Cod sursa(job #1491004)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 24 septembrie 2015 16:51:55
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.24 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;
}