Cod sursa(job #560135)

Utilizator APOCALYPTODragos APOCALYPTO Data 18 martie 2011 12:40:44
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define nmax 50010
#define pb push_back
ofstream fout("ctc.out");

vector<int> G[nmax];
vector<int> GT[nmax];
vector<int> comp;
vector<vector<int> > sol;
int N,M;
int viz1[nmax],viz2[nmax];
stack<int> s;

void dfs1(int x)
{
    if(viz1[x]) return;
    viz1[x]=1;

    vector<int>::iterator it;
    for(it=G[x].begin();it<G[x].end();it++)
    {
        dfs1(*it);
    }
    s.push(x);
}

void dfs2(int x)
{
    if(viz2[x]) return;
    viz2[x]=1;
    comp.pb(x);
    vector<int>::iterator it;
    for(it=GT[x].begin();it<GT[x].end();it++)
    {
        dfs2(*it);
    }
}

void solve()
{
    int i;
    for(i=1;i<=N;i++)
    {
        if(!viz1[i])
        {
            dfs1(i);
        }
    }

    int u;
    while(!s.empty())
    {
        u=s.top();
        s.pop();
       // cout<<u<<"\n";
        if(!viz2[u])
        {   comp.clear();
            dfs2(u);
            sol.pb(comp);
        }
    }
    fout<<sol.size()<<"\n";
    vector<vector<int> >::iterator it;
    vector<int>::iterator jt;
    for(it=sol.begin();it<sol.end();it++)
    {
        for(jt=it->begin();jt<it->end();jt++)
        {
            fout<<*jt<<" ";
        }
        fout<<"\n";
    }
}

void cit()
{
    ifstream fin("ctc.in");
    int i,x,y;
    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;

}