Cod sursa(job #1314184)

Utilizator cristigrigoreGrigore Cristan Andrei cristigrigore Data 11 ianuarie 2015 16:52:03
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int i,j,m,n,x,y,nr;
bool ok[100001],ok1[100000];;
stack <int> S;
vector <int> v[100011],v1[100011];
queue <int> S1;
void df(int k)
{
    ok[k]=true;
    S.push(k);
    vector <int>::iterator it;
    for(it=v[k].begin(); it!=v[k].end(); it++)
        if(!ok[*it]) df(*it);
}
void df1(int k)
{
    ok1[k]=true;
    S1.push(k);
    vector <int>::iterator it;
    for(it=v1[k].begin(); it!=v1[k].end(); it++)
        if(!ok1[*it]) df1(*it);
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d",&x,&y);
        v[x].push_back(y);
        v1[y].push_back(x);
    }
    for(i=1; i<=n; i++)
        if(!ok[i])df(i);
    while(!S.empty())
    {
        x=S.top();
        S.pop();
        if(!ok1[x])
        {
            nr++;
            df1(x);
            S1.push(-1);
        }
    }
    printf("%d\n",nr);
    while(!S1.empty())
    {
        x=S1.front();
        if(x==-1) printf("\n");
        else printf("%d ",x);
        S1.pop();
    }
    return 0;
}