Cod sursa(job #630255)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 5 noiembrie 2011 00:29:03
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<cstdio>
#include<vector>

using namespace std;
int n, m;
vector <int> LGraf[100001], LGrafInv[100001], S[100001];
int viz1[100001], viz2[100001];

void DF(int k, vector <int> *L, int *viz)
{
	unsigned int i;
	
	viz[k] = 1;

	for(i = 0; i < L[k].size(); i++)
		if(viz[L[k][i]] == 0) {
			viz[L[k][i]] = 1;
			DF(L[k][i], L, viz);
		}
}

int main() {
	int i, j, x, y, nr;
	
	freopen("ctc.in", "r", stdin), freopen("ctc.out", "w", stdout);
	scanf("%d %d", &n, &m);
	
	for(i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		LGraf[x].push_back(y);
		LGrafInv[y].push_back(x);
	}
	
	nr = 0;
	for(i = 1; i <= n; i++) {
		if(viz1[i] == 0) {
			DF(i, LGraf, viz1);
			DF(i, LGrafInv, viz2);
			
			bool inc = false;
			for(j = 1; j <= n; j++)
				if(viz1[j] == 1 && viz2[j] == 1) {
					viz1[j] = viz2[j] = 2; 
					if(!inc) { nr++; inc = true; }
					S[nr].push_back(j);
				}
				else if(viz1[j] == 1 || viz2[j] == 1) viz1[j] = viz2[j] = 0;
		}
	}
	
	printf("%d\n", nr);
	for(i = 1; i <= nr; i++) {
		for(j = 0; j < S[i].size(); j++)
			printf("%d ", S[i][j]);
		printf("\n");
	}
		
	return 0;
}