scc.cpp

acm 常用算法和代码库

#include <stdio.h>
#include <string.h>
#define G_size 100000
#define V_size 11000

typedef struct Graph
{
    int id;
    int next;
} Graph;

typedef struct Edge
{
    int s, e;
} Edge;

Edge E[G_size];
Graph GA[G_size], GT[G_size];
int N, M;
int G_end;
int order[V_size], id[V_size], vis[V_size], in[V_size],used[V_size];
int cnt, scnt, pos;
int newG[300][300]={0};
void Insert(int s, int e) //???????
{
    int p;
    p = s;
    while (GA[p].next)
        p = GA[p].next;
    GA[G_end].id = e;
    GA[p].next = G_end;

    p = e;
    while (GT[p].next)
        p = GT[p].next;
    GT[G_end].id = s;
    GT[p].next = G_end;

    G_end++;
}

void DFST(int x) //???????
{
    int p, q;
    vis[x] = 1;
    p = GT[x].next;
    while (p)
    {
        q = GT[p].id;
        if (!vis[q])
            DFST(q);
        p = GT[p].next;
    }
    order[cnt++] = x;
}

void DFSA(int x) //???????
{
    int p, q;
    vis[x] = 1;
    id[x] = cnt;
    p = GA[x].next;
    while (p)
    {
        q = GA[p].id;
        if (!vis[q])
            DFSA(q);
        p = GA[p].next;
    }
}
class UFSet {
public:
        long parent[V_size];
        void makeSet();
        long find(long);
        int cnt;
        bool unionSet(long, long);
};
void UFSet::makeSet() {
        memset(parent, -1, sizeof(parent));
        cnt=0;
}
long UFSet::find(long x) {
        if(parent[x] == -1) {
                return x;
        } else {
                parent[x] = find(parent[x]);
                return parent[x];
        }
}
bool UFSet::unionSet(long x, long y) {
        long pX = find(x);
        long pY = find(y);
        //if(pX==x) cnt++;
        
        if(pX != pY) {
                parent[pX] = pY;
                return true;
        }
        return false;
}
void Solve()  
{
    int s, e,p;
    int i;

    memset(GA, 0, sizeof(GA));
    memset(GT, 0, sizeof(GT));
    memset(E, 0, sizeof(E));
    memset(newG, 0, sizeof(newG));
    G_end = N + 1;

    for (i = 0; i < M; i++)
    {
        scanf("%d %d", &s, &e);
        E[i].s = s - 1;
        E[i].e = e - 1;
        Insert(s - 1, e - 1);
    }

    memset(vis, 0, sizeof(vis));
    cnt = 0;
    for (i = 0; i < N; i++)
    {
        if (!vis[i])
        {
            DFST(i);
        }
    }

    memset(vis, 0, sizeof(vis));
    cnt = 0;
    for (i = N - 1; i >= 0; i--)
    {
        if (!vis[order[i]])
        {
            DFSA(order[i]);
            cnt++;
        }
    }
      
 
    UFSet uset;
    uset.makeSet();
    
    for (i = 0; i < M; i++)
    {
        s = id[E[i].s];
        e = id[E[i].e];
        if (s != e)
        {
           uset.unionSet(s,e);
        }
    }
    bool flag=1;
    
    for(i=1;i<cnt;i++)
    {
        if(uset.find(i)!=uset.find(i-1))
           flag=false;
    }
    
    if(flag) printf("Yes\n");
    else printf("No\n");
    
}

int main()
{
    int cases;
    scanf("%d",&cases);
    while (cases--)
    {
        scanf("%d %d", &N, &M);
        Solve();
    
    }
    return 0;
}