Cod sursa(job #797627)

Utilizator marinMari n marin Data 14 octombrie 2012 15:29:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 100010


using namespace std;

vector <int> L[DIM];
vector <int> P[DIM];

int viz[DIM];
int low[DIM];
int stack[DIM];

int N, M, i, j, x, y, s, next, ctc;


void dfs(int x) {
	next++;
	viz[x] = next;
	low[x] = next;
	stack[++s] = x;
	int i, sz;
	for (i=0, sz = L[x].size(); i<sz; i++) {
		if (!viz[L[x][i]]) {
			dfs(L[x][i]);
			low[x] = min(low[x], low[L[x][i]]);
		} else
			if (viz[L[x][i]] > 0)
				low[x] = min(low[x], low[L[x][i]]);
	}
	if (low[x] == viz[x]) {
		int v;
		ctc++;
		do {
			v = stack[s--];
			viz[v] = - viz[v];
			P[ctc].push_back(v);
		} while (v!=x);
	}
}

int main() {
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	
	f>>N>>M;
	for (i=1;i<=M;i++) {
		f>>x>>y;
		L[x].push_back(y);
	}
	
	for (i=1;i<=N;i++)
		if (viz[i] == 0) {
			dfs(i);
		}
	g<<ctc<<"\n";
	for (i=1;i<=ctc;i++) {
		for (j=0;j<P[i].size();j++)
			g<<P[i][j]<<" ";
		g<<"\n";
	}
	f.close();
	g.close();
	return 0;
}