Cod sursa(job #964834)

Utilizator misinozzz zzz misino Data 22 iunie 2013 14:13:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<fstream>
#include<deque>
#include<set>
#include<vector>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int nrc,nrcc,i,n,m,x,y,viz[100100];
vector<int>l1[100100],l2[100100];
set<int>sol[100100];
deque<int>a;
inline void dfs(int x)
{
    viz[x]=nrc;
    for(vector<int>::iterator it=l1[x].begin();it!=l1[x].end();++it)
    if(!viz[*it])
    {
        dfs(*it);
    }
    a.pb(x);
}
inline void dfs1(int x)
{
    sol[nrcc].insert(x);
    for(vector<int>::iterator it=l2[x].begin();it!=l2[x].end();++it)
    {
        if(viz[*it]==nrc)
        {
            viz[*it]=0;
            dfs1(*it);
        }
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        l1[x].pb(y);
        l2[y].pb(x);
    }
    for(i=1;i<=n;++i)
    if(!viz[i])
    {
        ++nrc;
        dfs(i);
    }
    while(!a.empty())
    {
        while(!a.empty()&&!viz[a.back()])
        a.pop_back();
        if(a.empty())
        break;
        ++nrcc;
        nrc=viz[a.back()];
        viz[a.back()]=0;

        dfs1(a.back());
    }
    g<<nrcc<<'\n';
    for(i=1;i<=nrcc;++i)
    {
//        g<<sol[i].size()<<' ';
        for(set<int>::iterator it=sol[i].begin();it!=sol[i].end();++it)
        g<<*it<<' ';
        g<<'\n';
    }
    return 0;
}