Cod sursa(job #1413535)

Utilizator vasica38Vasile Catana vasica38 Data 1 aprilie 2015 22:16:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<stack>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

typedef struct lista
{
    int info;
    lista *next;
} * nod;
vector <int> ctc[100001];
stack  <int> st;
nod a[100001];
nod b[100001];
bool viz[100001];

int nr,i,j,k,m,n,u;
void add(int x, nod &p)
{
    nod r=new lista;
    r->info=x;
    r->next=p;
    p=r;
}


void dfs1(int x)
{
    viz[x]=1;
    nod r=a[x];
    while (r)
    {
        if (!viz[r->info]) dfs1(r->info);
        r=r->next;
    }
    st.push(x);
}


void dfs2(int x)
{
    viz[x]=0;
    nod r=b[x];
    while (r)
    {
        if (viz[r->info])
            {
                dfs2(r->info);
                ctc[nr].push_back(r->info);
            }
        r=r->next;
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; ++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(y,a[x]);
        add(x,b[y]);
    }
    for (i=1; i<=n; ++i)
        if (!viz[i]) dfs1(i);
    while (st.size())
    {
        if (viz[st.top()]) ctc[++nr].push_back(st.top()),dfs2(st.top());
        st.pop();
    }
    printf("%d\n",nr);
    for (i=1; i<=nr; ++i) {
        for (j=0; j<ctc[i].size(); ++j) printf("%d ",ctc[i][j]);
        printf("\n");
    }



    return 0;
}