Cod sursa(job #1185794)

Utilizator misinozzz zzz misino Data 16 mai 2014 21:33:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<deque>
#include<vector>

#define N 100100

using namespace std;

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

int n,m,i,x,y,nrctc,viz[N];

vector<int>v[N],vt[N],sol[N];

deque<int>dq;

inline void dfs(int x){
    viz[x] = 1;

    for(vector<int>::iterator it = v[x].begin() ; it != v[x].end() ; ++ it)
        if(!viz[*it])
        dfs(*it);

    dq.push_back(x);
}

inline void dfs1(int x){
    viz[x] = 0;
    sol[nrctc].push_back(x);

    for(vector<int>::iterator it = vt[x].begin() ; it != vt[x].end() ; ++ it)
        if(viz[*it])
        dfs1(*it);
}

int  main()
{
    f >> n >> m;

    for(i = 1 ; i <= m ; ++ i)
    {
        f >> x >> y;

        v[x].push_back(y);

        vt[y].push_back(x);
    }

    for(i = 1 ; i <= n ; ++ i)
        if(!viz[i])
        dfs(i);

    while(!dq.empty())
    {
        while(!dq.empty() && !viz[dq.back()])
            dq.pop_back();

        if(dq.empty())
            break;

        ++ nrctc;

        dfs1(dq.back());
    }

    g << nrctc << '\n';

    for(i = 1 ; i <= nrctc ; ++ i , g << '\n')
        for(vector<int>::iterator it = sol[i].begin() ; it != sol[i].end() ; ++ it)
        g << *it << ' ';

    return 0;
}