Cod sursa(job #1521845)

Utilizator DacianBocea Dacian Dacian Data 10 noiembrie 2015 21:36:11
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <vector>
#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
vector<int> No[100001];
vector<vector<int>> conc;
int index[100001], lowlink[100001], st[100001], len=0,ind=1,k; 
bitset<100001> v;
ifstream f("ctc.in");
ofstream of("ctc.out");
ios_base::sync_with_stdio(false);
void dfs(const int& x){
	index[x] = ind;
	lowlink[x] = ind++;
	st[len++] = x;
	v[x] = 1;
	for (const auto&j : No[x]){
		if (!index[j]){
			dfs(j);
			lowlink[x] = min(lowlink[x], lowlink[j]);
		}
		else if (v[j]) lowlink[x] = min(lowlink[x], index[j]);
	}
	if (lowlink[x] == index[x]){
		conc.push_back(vector<int>());
		do{
			k = st[--len];
			v[k] = 0;
			conc[conc.size() - 1].push_back(k);	
		} while (x != k);
	}
}
int main(){
	int N, M,a,b;
	f >> N >> M;
	for (int i = 0; i < M; ++i){
		f>>a>>b;
		No[a].push_back(b);
	}
	for (int i = 1; i <= N;++i)
	if (!index[i])dfs(i);

	of << conc.size()<<"\n";
	for (const auto&j:conc){
	for (const auto&d : j)
		of << d << " ";
	of << "\n";
	}
}