Cod sursa(job #2295512)

Utilizator q1e123Solca Robert-Nicolae q1e123 Data 3 decembrie 2018 18:30:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include<cstdio>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cstring>

#define MAX 100001
#define pb push_back

using std::vector;
using std::bitset;

int n,m,nr;

vector<int> graph[MAX], graphTrans[MAX],scc[MAX] , stack;
bitset<MAX> viz;

void order(int node){
	viz[node] = true;
	for(auto i:graph[node]){
		if(!viz[i]) order(i);
	}
	stack.pb(node);
}
int k;
void DFS(int node){
	viz[node] = true;
	scc[k].pb(node);
	for(auto i:graphTrans[node]){
		if(!viz[i]) DFS(i);
	}
}

int main(){
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);

	scanf("%d %d",&n,&m);
	for(int i=0;i<m;++i){
		int x,y;
		scanf("%d %d",&x,&y);
		graph[x].pb(y);
		graphTrans[y].pb(x);
	}
	
	//phase I
	for(int i=1;i<=n;++i){
		if(!viz[i]){
			++nr;
			order(i);
		}
	}

	//phase I to II
	for(int i=1;i<=n;++i) viz[i] = false;
	k=0;
	//phase II
	while(!stack.empty()){
		int vertex=stack.back();
		stack.pop_back();
		if(!viz[vertex]){
			++k;
			DFS(vertex);
		}
	}
	printf("%d\n",k);
	for(int i=1;i<=k;++i){
		for(auto it:scc[i]) printf("%d ",it);
		printf("\n");
	}
	return 0;
}