Cod sursa(job #1504786)

Utilizator UMihneaUngureanu Mihnea UMihnea Data 18 octombrie 2015 11:59:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <stack>
#define N 100010

using namespace std;

vector<int> v[N], C[N];
bitset<N> U;
int n,m,x,y,i,c,k,Nr[N],X[N],Y[N];
void df(int);

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
    }
    x=y=0;
    for(i=1;i<=n;i++)
        if(!Nr[i])
            df(i);
    printf("%d\n",c);
    for(i=0;i<c;i++)
    {
        for(auto it : C[i])
            printf("%d ",it);
        printf("\n");
    }
    return 0;
}
void df(int nod)
{
    Nr[nod]=++k;
    X[++x]=nod;Y[++y]=nod;
    for(auto it : v[nod])
    {
        if(!Nr[it])
            {df(it);continue;}
        if(U[it])
            continue;
        while(Nr[Y[y]]>Nr[it])
            y--;
    }
    if(Y[y]==nod)
    {
        for(;;)
        {
            C[c].push_back(X[x]);
            U[X[x]]=1;
            if(X[x]==nod)
                break;
            x--;
        }
        x--;y--;c++;
    }
}