Cod sursa(job #2143017)

Utilizator DimaTCDima Trubca DimaTC Data 25 februarie 2018 14:52:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<bits/stdc++.h>
#define NMAX 100010
using namespace std;

vector<int>V[NMAX];
bool inStack[NMAX];
int disc[NMAX], low[NMAX];
stack<int>S;
int n,m,nr;
vector<int>::iterator it;
vector<int>CTC[NMAX];
int rs;
int u;

void tarjan(int x) {
	disc[x]=++nr;
	low[x]=nr;
	S.push(x);
	inStack[x]=1;
	
	for (int i=0; i<V[x].size(); i++) {
		int y=V[x][i]; 
		if (disc[y]==0) { 
			tarjan(y);
			low[x] = min(low[x], low[y]);
		} else if (inStack[y]) {
			low[x] = min(low[x], disc[y]);
		}
	} 
	
	if (disc[x]==low[x]) {
		rs++;
		do {
			u=S.top();
			S.pop();
			CTC[rs].push_back(u);
			inStack[u]=0;
		} while (u!=x);
	}
}

int main() {
	ifstream cin("ctc.in");
	ofstream cout("ctc.out");
	cin>>n>>m;
	
	for (int i=1; i<=m; i++) {
		int x,y; cin>>x>>y;
		V[x].push_back(y);
	}
	
	for (int i=1; i<=n; i++) {
		if (!disc[i]) tarjan(i);
	}
	cout<<rs<<'\n';
	for (int i=1; i<=rs; i++) {
		for (it=CTC[i].begin(); it!=CTC[i].end(); ++it) cout<<*it<<" ";
		cout<<'\n';
	}
	
	return 0;
}


//DEBUG dc nu merge
	/*for (it=V[x].begin(); it!=V[x].end(); it++) {
		int y=*it; cout<<'.'<<y<<'.';
		if (disc[y]==0) { cout<<"e";
			tarjan(y);
		//	low[x] = min(low[x], low[y]);
		} /*else if (inStack[y]) {
			low[x] = min(low[x], disc[y]);
		}*/
//	}*/