Cod sursa(job #752655)

Utilizator adalLica Adela adal Data 29 mai 2012 09:43:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <vector>
#define pb push_back
#include <cstring>

using namespace std;

vector<int> G[100010],GT[100010];
int nc, nr, i, k, N, M, x, y, St[100010];
bool sel[100010];

void DF(int x){
int i;
  sel[x]=true;
  for(i = 0; i < G[x].size(); ++i)
    if (!sel[G[x][i]]) DF(G[x][i]);
  St[++nr]=x;
}

void DFT(int x, bool k){
int i;
  sel[x]=true;
  if (k) printf("%d ", x);
  for(i = 0; i < GT[x].size(); ++i)
    if (!sel[GT[x][i]]) DFT(GT[x][i], k);
}

int main(){

    freopen("ctc.in","r", stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d\n", &N, &M);
    for (i=1; i<=M; ++i){
        scanf("%d %d\n", &x, &y);
        G[x].pb(y);
        GT[y].pb(x);

    }
    nr=0; nc=0;
    memset(sel, false,sizeof(sel));
    for(i=1; i<=N; i++)
        if (!sel[i]) DF(i);
    memset(sel, false,sizeof(sel));
    for(i=N; i>0; --i)
        if (!sel[St[i]])
        {
            DFT(St[i], false);
            nc++;
        }
    printf("%d\n", nc);
    memset(sel, false,sizeof(sel));
    for(i=N; i>0; --i)
        if (!sel[St[i]])
        {
            DFT(St[i], true);
            printf("\n");
        }
    return 0;
}