Cod sursa(job #1050951)

Utilizator hevelebalazshevele balazs hevelebalazs Data 9 decembrie 2013 14:58:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <vector>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define N 100000
using namespace std;
vector<int>o[N],O[N];
int l[N],s,nr;
bool c[N];
void dfs(int i){
    if(c[i])return;
    c[i]=true;
    int m=o[i].size();
    fr(j,0,m) dfs(o[i][j]);
    l[--s]=i;
    }
int dfsn(int i){
    if(!c[i])return 0;
    c[i]=false;
    int m=O[i].size();
    fr(j,0,m)dfsn(O[i][j]);
    return 1;
    }
bool dfs2(int i){
    if(c[i])return false;
    printf("%i ",i+1);
    c[i]=true;
    int m=O[i].size();
    fr(j,0,m) dfs2(O[i][j]);
    return true;
    }
int main(){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m,x,y;
    scanf("%i%i",&n,&m);
    s=n;
    fr(i,0,m)scanf("%i%i",&x,&y),o[x-1].push_back(y-1),O[y-1].push_back(x-1);
    fr(i,0,n)dfs(i);
    fr(i,0,n)nr+=dfsn(l[i]);
    printf("%i\n",nr);
    fr(i,0,n)if(dfs2(l[i]))printf("\n");
    return 0;
    }