Cod sursa(job #1490979)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 24 septembrie 2015 16:03:44
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <string.h>
#include <algorithm>

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 indx[Nmax], lowLink[Nmax], ptr;
bitset <Nmax> onStack;
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;
}

void dfs(int node)
{
	indx[node] = lowLink[node] = ++ptr;
	stack[s++] = node;
	onStack[node] = 1;

	for (int i = adj[node]; ~i; i = l[i].next)
	{
		int son = l[i].v;
		if (!indx[son])
		{
			dfs(son);
			lowLink[node] = min(lowLink[node], lowLink[son]);
		}
		else if (onStack[son])
			lowLink[node] = min(lowLink[node], lowLink[son]);
	}
	if (indx[node] == lowLink[node])
	{
		int v;
		do
		{
			v = stack[--s];
			sccBuff[sccPtr].v = v;
			sccBuff[sccPtr].next = scc[sccCount];
			scc[sccCount] = sccPtr++;
		} while (v != node);
		sccCount++;
	}
}

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 (!indx[i])
			dfs(i);
	}

	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;
}