Cod sursa(job #1216164)

Utilizator EpictetStamatin Cristian Epictet Data 3 august 2014 15:48:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y, nr, k, Level[100010], LowLink[100010];
bool In[100010];
vector < int > V[100010], Sol[100010];
stack < int > S;

inline void Tarjan(int nod)
{
    Level[nod] = LowLink[nod] = ++k;
    S.push(nod);
    In[nod] = 1;

    for (vector < int > :: iterator it = V[nod].begin(); it != V[nod].end(); it++)
    {
        if (!Level[*it]) Tarjan(*it);
        if (In[*it]) LowLink[nod] = min(LowLink[nod], LowLink[*it]);
    }

    if (LowLink[nod] == Level[nod])
    {
        nr++;
        while (true)
        {
            Sol[nr].push_back(S.top());
            In[S.top()] = 0;
            S.pop();
            if (Sol[nr][Sol[nr].size() - 1] == nod) break;
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        fin >> x >> y;
        V[x].push_back(y);
    }

    for (int i=1; i<=n; i++)
    {
        if (!Level[i])
        {
            Tarjan(i);
        }
    }

    fout << nr << '\n';
    for (int i=1; i<=nr; i++)
    {
        for (vector < int > :: iterator it = Sol[i].begin(); it != Sol[i].end(); it++)
            fout << *it << ' ';
        fout << '\n';
    }

    fout.close();
    return 0;
}