Cod sursa(job #1504782)

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

using namespace std;

vector<int> v[N], C[N];
stack<int> S, P;
bitset<N> U;
int n,m,x,y,i,c,k,Nr[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);
    }
    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;
    S.push(nod);
    P.push(nod);
    for(auto it : v[nod])
    {
        if(!Nr[it])
            {df(it);continue;}
        if(U[it])
            continue;
        while(Nr[P.top()]>Nr[it])
            P.pop();
    }
    if(P.top()==nod)
    {
        for(;;)
        {
            C[c].push_back(S.top());
            U[S.top()]=1;
            if(S.top()==nod)
                break;
            S.pop();
        }
        S.pop();
        P.pop();
        c++;
    }
}