Cod sursa(job #1961364)

Utilizator andrei232000Andrei Maria andrei232000 Data 11 aprilie 2017 08:25:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct Nod
{
    int index, lowlink;
    bool onStack;
};
int g, N, M, i, j, index, x, y;
stack<int> S;
vector<int> e[100003];
vector<int> sct[100003];
Nod n[100003];
void strongConnect(int v)
{
    int w, si;
    ++index;
    n[v].index = index;
    n[v].lowlink = index;
    S.push(v);
    n[v].onStack = true;
    for(si = 0; si < e[v].size(); ++si)
    {
        w = e[v][si];
        if(n[w].index == 0)
        {
            strongConnect(w);
            n[v].lowlink = min(n[w].lowlink, n[v].lowlink);
        }
        else if(n[w].onStack)
        {
            n[v].lowlink = min(n[w].lowlink, n[v].lowlink);
        }
    }
    if(n[v].index == n[v].lowlink)
    {
        do
        {
            w = S.top();
            S.pop();
            n[w].onStack = false;
            sct[g].push_back(w);
        }
        while(v != w);
        ++g;
    }
}
int main()
{
    fin>>N>>M;
    for(i = 0; i < M; ++i)
    {
        fin>>x>>y;
        e[x].push_back(y);
    }
    for(i = 1; i <= N; ++i)
    {
        if(n[i].index == 0)
        {
            strongConnect(i);
        }
    }
    fout<<g<<'\n';
    for(i = 0; i < g; ++i)
    {
        for(j = 0; j < sct[i].size(); ++j)
        {
            fout<<sct[i][j]<<" ";
        }
        fout<<'\n';
    }
    return 0;
}