Cod sursa(job #1550394)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 13 decembrie 2015 17:34:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <deque>
#define NN 100001
//#define x first
//#define y second
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int lowidx[NN],in_stack[NN],idx[NN],indexx,n,m,i,j;
vector < int > v[NN],curent;
vector < vector <int> > solutii;
stack <int> S;
void tarjan(int nod)
{
    int i;
    indexx ++;
    lowidx[nod] = idx[nod] = indexx;
    S.push(nod);
    in_stack[nod] = 1;

    for(i = 0; i < v[nod].size(); i ++)
    {
        int nxt = v[nod][i];
        if(!idx[nxt])
        {
            tarjan(nxt);
            lowidx[nod] = min(lowidx[nod], lowidx[nxt]);
        }
        else if(in_stack[nxt])
        {
            lowidx[nod] = min(lowidx[nod], lowidx[nxt]);
        }
    }

    if(lowidx[nod] == idx[nod])
    {
        int now;
        do
        {
            now=S.top();
            curent.push_back(now);
            in_stack[now]=0;
            S.pop();
        }while(now != nod);
        solutii.push_back(curent);
        curent.clear();
    }

}
int main()
{
    fin >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        int a,b;
        fin >> a >> b;
        v[a].push_back(b);
    }

    for(i = 1; i <= n; i ++)
    {
        if(!idx[i])
            tarjan(i);
    }

    fout << solutii.size() << '\n';
    for(i = 0; i < solutii.size(); i ++, fout << '\n')
        for(j = 0; j < solutii[i].size(); j ++)
            fout << solutii[i][j] << ' ';

return 0;
}