Cod sursa(job #1552876)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 18 decembrie 2015 20:43:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <vector>
#define MAX 100005
using namespace std;

int n, m, a, b, root[MAX], nr;
vector<int> Gout[MAX], Gin[MAX], L, G[MAX];
bool viz[MAX];

void dfs(int u){
	viz[u] = 1;
	for(int i = 0; i < Gout[u].size(); i++)
		if(!viz[Gout[u][i]])
			dfs(Gout[u][i]);
	L.push_back(u);
}

void dfsBack(int u, int r){
	root[u] = r;
	for(int i = 0; i < Gin[u].size(); i++)
		if(!root[Gin[u][i]])
			dfsBack(Gin[u][i], r);
}

int main(){
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++){
		scanf("%d%d", &a, &b);
		Gout[a].push_back(b);
		Gin[b].push_back(a);
	}
	for(int i = 1; i <= n; i++)
		if(!viz[i])
			dfs(i);
	for(; L.size(); L.pop_back())
		if(!root[L.back()])
			dfsBack(L.back(), ++nr);
	for(int i = 1; i <= n; i++)
		G[root[i]].push_back(i);
	printf("%d\n", nr);
	for(int i = 1; i <= nr; i++){
		for(int j = 0; j < G[i].size(); j++)
			printf("%d ", G[i][j]);
		printf("\n");
	}
	return 0;
}