Cod sursa(job #2381913)

Utilizator _Victor_Victor Ciobanu _Victor_ Data 17 martie 2019 14:12:27
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define NMAX 100010
//Algoritmul lui Tarjan pentru determinarea componentelor tare conexe

using namespace std;

vector <int> A[NMAX],CTC[NMAX],S;
int n,m,noc=0,idc=1,id[NMAX],low[NMAX];
bool in_stack[NMAX];

void Tarjan(int u){
	S.push_back(u);
	in_stack[u]=1;
	id[u]=low[u]=idc++;
	for(int i=0;i<A[u].size();i++){
		int v=A[u][i];
		if(!id[v]){
			Tarjan(v);
		}
		if(in_stack[v])low[u]=min(low[u],low[v]);
	}
	if(id[u]==low[u]){
		int c=S.back();
		while(c!=u){
			S.pop_back();
			CTC[noc].push_back(c);
			in_stack[c]=0;
			c=S.back();	
		}
		CTC[noc++].push_back(u);
		S.pop_back();
	}
}

int main(){
	ifstream cin("ctc.in");
	ofstream cout("ctc.out");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		A[a].push_back(b);
	}
	for(int i=1;i<=n;i++){
		if(!id[i])Tarjan(i);
	}
	cout<<noc<<'\n';
	for(int i=0;i<noc;i++){
		for(int j=0;j<CTC[i].size();j++){
			cout<<CTC[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}