Cod sursa(job #481669)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 1 septembrie 2010 12:48:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

int nr,N,M,Tr[100001],s;

vector<int>G[100001];
vector<int>Gt[100001];
vector<int>Ctc[100001];

bool Viz[100001];

inline void DFS(int nod)
{
    int i;
    Viz[nod] = 1;
    for(i=0;i<G[nod].size();i++)
        if(!Viz[G[nod][i]])
            DFS(G[nod][i]);
    Tr[s++]=nod;
}

inline void DFS2(int nod)
{
    int i;
    Viz[nod] = 0;
    for(i=0;i<Gt[nod].size();i++)
        if(Viz[Gt[nod][i]])
            DFS2(Gt[nod][i]);
    Ctc[nr].push_back(nod);
}
int main()
{
    int i,j,x,y;
    in>>N>>M;
    while(M--)
    {
        in>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(i=1;i<=N;i++)
        if(!Viz[i])
            DFS(i);
    for(i=N;i>0;i--)
        if(Viz[Tr[i]])
        {
            DFS2(Tr[i]);
            nr++;
        }
    out<<nr<<'\n';
    for(i=0;i<nr;i++)
    {
        for(j=0;j<Ctc[i].size();j++)
            out<<Ctc[i][j]<<' ';
        out<<'\n';
    }
    return 0;
}