Cod sursa(job #1491006)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 24 septembrie 2015 16:52:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <string.h>
#include <algorithm>
#include <bitset>
 
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];
 onStack[v] = 0;
 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;
}