Cod sursa(job #1951362)

Utilizator wilson182Alexandrina Panfil wilson182 Data 3 aprilie 2017 16:18:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<bits/stdc++.h>
using namespace std;
const int N=100020;
vector <int> lda[N], ldt[N], l, lc[N];
int v1[N], v2[N], nc;
void dfs1(int nod){
	v1[nod]=1;
	int x=lda[nod].size();
	for(int i=0;i<x;i++) if(!v1[lda[nod][i]]){
		dfs1(lda[nod][i]);
	}
	l.push_back(nod);
}
void dfs(int nod){
	int x=ldt[nod].size();
	v2[nod]=1;
	for(int i=0;i<x;i++) if(!v2[ldt[nod][i]])dfs(ldt[nod][i]);
	lc[nc].push_back(nod);
}
int main(){
    int n, m;
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
	scanf("%d%d", &n, &m);
	int x, y;
	while(m--){
		scanf("%d%d", &x, &y);
		lda[x].push_back(y);
		ldt[y].push_back(x);
	}
	for(int i=1;i<=n;i++)if(!v1[i]) dfs1(i);
	for(int i=l.size()-1; i>=0;i--) if(!v2[l[i]]){
		nc++;
		dfs(l[i]);
	}
	printf("%d\n", nc);
	for(int i=1;i<=nc;i++){
		int x=lc[i].size();
		for(int j=0;j<x;j++) printf("%d ", lc[i][j]);
		printf("\n");
	}
	return 0;
}