Cod sursa(job #527064)

Utilizator APOCALYPTODragos APOCALYPTO Data 30 ianuarie 2011 15:54:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define pb push_back
#define nmax 100005
ofstream fout("ctc.out");
vector<int> G[nmax],GT[nmax],ans[nmax];
stack<int> s;
int N,M,viz[nmax],nr=0;;
void DFS(int u)
{
    if(viz[u]) return;
    viz[u]=1;
    vector<int>::iterator it;
    for(it=G[u].begin();it<G[u].end();it++)
    {
        DFS(*it);
    }
    s.push(u);
}


void DFS2(int u)
{
    if(!viz[u]) return;
    viz[u]=0;
    vector<int>::iterator it;
    for(it=GT[u].begin();it<GT[u].end();it++)
    {
        DFS2(*it);
    }
    ans[nr].pb(u);
}
void solve()
{   int i;
    for(i=1;i<=N;i++)
    if(!viz[i])
    {
        DFS(i);
    }
    int u;

    while(!s.empty())
    {
        u=s.top();

        s.pop();
        if(viz[u])
        {   nr++;
            DFS2(u);
        }
    }
    fout<<nr<<"\n";
    vector<int>::iterator it;
    for(i=1;i<=nr;i++)
    {
        for(it=ans[i].begin();it<ans[i].end();it++)
        {
            fout<<*it<<" ";
        }
        fout<<"\n";
    }


}

void cit()
{
    int i,x,y;
    ifstream fin("ctc.in");
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        G[x].pb(y);
        GT[y].pb(x);
    }
    fin.close();
}

int main()
{
    cit();
    solve();

    fout.close();
    return 0;
}