Cod sursa(job #630282)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 5 noiembrie 2011 02:47:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<cstdio>
#include<vector>

using namespace std;

int n, m, index = 1, nrComp = 0;
vector <int> graf[100001], S, vindex(100001), lowlink(100001, 200001);
vector <int> compCurenta(100001), viz(100001);

inline int min(const int &a, const int &b) {
	return (a < b ? a : b);
}

void SCC(int nod){
	
	S.push_back(nod);
	vindex[nod] = index;
	lowlink[nod] = index++;
	compCurenta[nod] = 1;
	viz[nod] = 1;
	int i, adiacent;
	
	for (i = 0; i < (int) graf[nod].size(); i++){
		adiacent = graf[nod][i];
		
		if (vindex[adiacent] == 0) {
			SCC( adiacent );
			lowlink[nod] = min (lowlink[adiacent], lowlink[nod]);
		}
		else if (compCurenta[adiacent] == 1)
			lowlink[nod] = min (vindex[adiacent], lowlink[nod]);
		
	}
	
	if (lowlink[nod] == vindex[nod]){
		nrComp++;
		do {
			adiacent = S[S.size() - 1];
			S.pop_back();
			compCurenta[adiacent] = 0;
			printf("%d ", adiacent);			
		}
		while (nod != adiacent);
		printf("\n");
	}
}

int main(){
	
	freopen("ctc.in", "r", stdin), freopen("componente.txt", "w", stdout);
	scanf("%d %d", &n, &m);
	
	int i, x, y;
	for (i = 0; i < m; i++) {
		scanf("%d %d", &x, &y);
		graf[x].push_back(y);
	}
	
	for (i = 1; i <= n ; i++){
		if (!viz[i]) SCC(i);
	}
	
	fclose(stdin), fclose(stdout);
	freopen("componente.txt", "r", stdin), freopen("ctc.out", "w", stdout);
	printf ("%d\n", nrComp);

		char line[1000001];
		scanf("%1000000[0-9 \n]s", line);
		printf("%s\n", line);
		
	fclose(stdin), fclose(stdout);
	
	return 0;
}