Cod sursa(job #529493)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 5 februarie 2011 12:02:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<vector>
using namespace std;
const int N=100005;
int ctc,q,n,m,v[N],poz[N];
bool f[N];
vector<int> L[N],LT[N],rez[N];
void read()
{
    int x,y;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        L[x].push_back(y);
        LT[y].push_back(x);
    }
}
void makevec(int nod)
{
    f[nod]=true;
    for(vector<int>::iterator it=L[nod].begin();it!=L[nod].end();it++)
        if(!f[*it])
            makevec(*it);
    v[++q]=nod;
    poz[nod]=q;
}
void init()
{
    for(int i=1;i<=n;i++)
        if(!f[i])
            makevec(i);
}
void reset(bool f[N])
{
    for(int i=1;i<=n;i++)
        f[i]=false;
}
void dfs(int nod)
{
    f[poz[nod]]=true;
    for(vector<int>::iterator it=LT[nod].begin();it!=LT[nod].end();it++)
        if(!f[poz[*it]])
            dfs(*it);
    rez[ctc].push_back(nod);
}
void solve()
{
    for(int i=n;i>=1;i--)
        if(!f[i])
        {
            ctc++;
            dfs(v[i]);
        }
}
void afis()
{
    printf("%d\n",ctc);
    for(int i=1;i<=ctc;i++)
    {
        for(vector<int>::iterator it=rez[i].begin();it!=rez[i].end();it++)
            printf("%d ",*it);
        printf("\n");
    }
}
int main()
{
    read();
    init();
    reset(f);
    solve();
    afis();
    return 0;
}