Cod sursa(job #1491002)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 24 septembrie 2015 16:49:19
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <string.h>

using namespace std;

const int Nmax = 100000;
const int Mmax = 200000;
const int NIL = -1;

struct cell
{
	int v, next;
};

cell l[Mmax];
int adj[Nmax];

int d[Nmax];
bool onStack[Nmax];
int stack[Nmax], s;

cell sccBuff[Nmax];
int sccPtr;
int scc[Nmax], sccCount;

void addEdge(int u, int v, int pos)
{
	l[pos].v = v;
	l[pos].next = adj[u];
	adj[u] = pos;
}

int dfs(int u, int depth)
{
	d[u] = depth;
	stack[s++] = u;
	onStack[u] = 1;

	for (int i = adj[u]; ~i; i = l[i].next)
	{
		int v = l[i].v;
		if (!d[v])
			d[u] = min(d[u], dfs(v, depth + 1));
		else if (onStack[v])
			d[u] = min(d[u], d[v]);
	} 
	if (d[u] == depth)
	{
		int v;
		do
		{
			v = stack[--s];
			onStack[v] = 0;
			sccBuff[sccPtr].v = v;
			sccBuff[sccPtr].next = scc[sccCount];
			scc[sccCount] = sccPtr++;
		} while (v != u);
		sccCount++;
	}
	return d[u];
}

int main()
{
	ifstream in("ctc.in");
	ofstream out("ctc.out");
	in.tie(0);
	ios_base::sync_with_stdio(0);
	int n, m;
	int u, v;

	in >> n >> m;
	
	memset(adj, NIL, sizeof(adj));
	memset(scc, NIL, sizeof(scc));

	for (int i = 0; i < m; i++)
	{
		in >> u >> v;
		addEdge(u - 1, v - 1, i);
	}
	in.close();

	for (int i = 0; i < n; i++)
	{
		if (!d[i])
			dfs(i, 1);
	}

	out << sccCount << '\n';
	for (int i = 0; i < sccCount; i++)
	{
		for (int j = scc[i]; ~j; j = sccBuff[j].next)
			out << sccBuff[j].v + 1 << ' ';
		out << '\n';
	}
	out.close();
	return 0;
}