Cod sursa(job #872241)

Utilizator mihai27Mihai Popescu mihai27 Data 5 februarie 2013 21:47:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<fstream>
#include<vector>
#include<string.h>

using namespace std;

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

int nr,n,m,i,j,x,y,ok[100001];
vector<int> b[100001],a[100001],sol[100001],Q;

void DF1(int nod)
{
    ok[nod]=1;
    for (vector<int>::iterator it=a[nod].begin();it!=a[nod].end();it++)
        if (!ok[*it]) DF1(*it);
    Q.push_back(nod);
}

void DF2(int nod)
{
    ok[nod]=1;
    sol[nr].push_back(nod);

    for (vector<int>::iterator it=b[nod].begin();it!=b[nod].end();it++)
        if (!ok[*it]) DF2(*it);
}

int main()
{
    in>>n>>m;
    for (i=1;i<=m;i++)
    {
        in>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for (i=1;i<=n;i++)
        if (!ok[i])
            DF1(i);

    memset(ok,0,sizeof(ok));

    for(i=Q.size()-1;i>=0;i--)
        if (!ok[Q[i]])
        {
            nr++;
            DF2(Q[i]);
        }
    out<<nr<<'\n';
    for (i=1;i<=nr;i++)
    {
        for (j=0;j<sol[i].size();j++)
            out<<sol[i][j]<<' ';
        out<<'\n';
    }
}