Cod sursa(job #1669283)

Utilizator alex.vasiuVasiu Alexandru alex.vasiu Data 30 martie 2016 16:54:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N_MAX = 100001;

vector <int> G[N_MAX];
vector <int> sol[N_MAX];
stack <int> S;

int lowlink[N_MAX];
bool in_stiva[N_MAX];
int n, m, index, total;
int idx[N_MAX];

void read()
{
    int x, y;
    f>>n>>m;
    for (int i=1; i<=m; i++)
       f>>x>>y,G[x].push_back(y);
}

void dfs(int nod)
{
    index++;
    idx[nod] = index;
    lowlink[nod] = index;
    S.push(nod);
    in_stiva[nod] = true;
    for (int i : G[nod])
        if (!lowlink[i])
            dfs(i), lowlink[nod] = min(lowlink[nod], lowlink[i]);

        else
            if (in_stiva[i])
                lowlink[nod] = min(lowlink[nod], lowlink[i]);

    if (lowlink[nod] == idx[nod])
    {
        int it;

        it = S.top();
        total ++;

        while (it != nod)
        {
            sol[total].push_back(it);
            in_stiva[it] = false;
            S.pop();
            it = S.top();
        }
        sol[total].push_back(it);
        S.pop();
        in_stiva[it] = false;
    }
}

void write()
{
    g<<total<<"\n";
    for (int i=1; i<=total; i++)
    {
        for (int j : sol[i])
           g<<j<<" ";
        g<<"\n";
    }
}

int main()
{
    read();
    for (int i=1; i<=n; i++)
    {
        if (!lowlink[i])
            dfs(i);
    }
    write();
    return 0;
}