Cod sursa(job #764872)

Utilizator test666013Testez test666013 Data 6 iulie 2012 16:17:36
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100001

vector<int>g[MAX],t[MAX];
queue<int>s;
queue<queue<int> >d;

int n,m;
bool was[MAX],l[MAX],r[MAX];

void l_dfs(int x){
    int y;
    l[x] = 1;
    for(int i=0;i<g[x].size();i++)
    {
        y = g[x][i];
        if( !l[y] && !was[y] )l_dfs(y);
    }
}

void r_dfs(int x){
    int y;
    r[x] = 1;
    for(int i=0;i<t[x].size();i++)
    {
        y = t[x][i];
        if( !r[y] && !was[y] )r_dfs(y);
    }
}

void find_components(){
    for(int i=1;i<=n;i++)
    if( !was[i] )
    {
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        l_dfs(i);
        r_dfs(i);
        for(int i=1;i<=n;i++)
        if( l[i] && r[i] )
        {
            s.push(i);
            was[i] = 1;
        }
        d.push(s);
        while( s.size() > 0 )s.pop();
    }
    printf("%d\n",d.size());
    while( d.size() > 0 )
    {
        while( d.front().size() > 0 )
        {
            printf("%d ",d.front().front());
            d.front().pop();
        }
        printf("\n");
        d.pop();
    }
}

int main(){
    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);
            g[x].push_back(y);
            t[y].push_back(x);
        }
    find_components();
    return 0;
}