HDU 1269(tarjan求强连通)

比眉伴天荒 2022-09-20 12:42 177阅读 0赞

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    #include <iostream>
    using namespace std;
    
    #define MAXE 100010
    #define MAXN 10010
    
    struct edge
    {
        int u, v, next;
    } edges[MAXE];
    
    int head[MAXN], cnt;
    int DFN[MAXN], LOW[MAXN], Stap[MAXN], Belong[MAXN];
    bool instack[MAXN];
    int Stop, Bcnt, Dindex;
    
    void add(int a, int b)
    {
        edges[cnt].u = a, edges[cnt].v = b;
        edges[cnt].next = head[a];
        head[a] = cnt++;
    }
    
    void tarjan(int u)
    {
        int v;
        DFN[u] = LOW[u] = ++Dindex;
        instack[u] = true;
        Stap[++Stop] = u;
        for (int e = head[u]; e != -1; e = edges[e].next)
        {
            v = edges[e].v;
            if (!DFN[v])
            {
                tarjan(v);
                if (LOW[v] < LOW[u])
                    LOW[u] = LOW[v];
            }
            else if (instack[v] && DFN[v] < LOW[u])
                LOW[u] = DFN[v];
        }
        if (DFN[u] == LOW[u])
        {
            Bcnt++;
            do
            {
                v = Stap[Stop--];
                instack[v] = false;
                Belong[v] = Bcnt;
            }while (v != u);
        }
    }
    
    void solve(int N)
    {
        Stop = Bcnt = Dindex = 0;
        memset(DFN, 0, sizeof(int) * (N + 1));
        memset(instack, false, sizeof(bool) * (N + 1));
        for (int u = 1; u <= N; ++u)
            if (!DFN[u])
                tarjan(u);
    }
    
    int main()
    {
        int N, M, a, b;
        while (scanf("%d%d", &N, &M) != EOF && N + M)
        {
            memset(head, -1, sizeof(int) * (N + 1));
            cnt = 0;
            while (M--)
            {
                scanf("%d%d", &a, &b);
                add(a, b);
            }
            solve(N);
            printf(Bcnt == 1 ? "Yes\n" : "No\n");
        }
    }