Cod sursa(job #1923084)

Utilizator blackoddAxinie Razvan blackodd Data 10 martie 2017 20:39:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define MaxN 100009

int n, m, ap[MaxN], nr;
bool viz[MaxN];
vector<int> G[MaxN], G_rev[MaxN], Ans[MaxN];
stack<int> st;

void Df(int i) {
	viz[i] = 1;
	for ( const auto x : G[i] ) 
		if ( !viz[x] ) 
			Df(x);
	st.push(i);
}

void Df2(int i) { 
	ap[i] = nr;
	for ( const auto x : G_rev[i] ) 
		if ( ap[x] == -1 ) 
			Df2(x);
}

int main() {
	fin >> n >> m;
	
	for ( int i = 1, x, y; i <= m; ++i ) {
		fin >> x >> y;
		G[x].push_back(y);
		G_rev[y].push_back(x);
	}
	
	for ( int i = 1; i <= n; ++i ) 
		if ( !viz[i] ) 
			Df(i);
			
	for ( int i = 1; i <= n; ++i ) {
		viz[i] = 0;
		ap[i] = -1;
	}
			
	while(!st.empty()){
		int x = st.top();
		if ( ap[x] == -1 ) {
			nr++;
			Df2(x);
		}
		st.pop();
	}
	
	for ( int i = 1; i <= n; ++i ) 
		Ans[ap[i]].push_back(i);
		
	fout << nr << '\n';
	
	for ( int i = 1; i <= n; ++ i ) {
		for ( const auto y : Ans[i] ) 
			fout << y << ' ';
		fout << '\n';
	}
	
}