Cod sursa(job #2278011)

Utilizator Alex03Runcan Alexandru Alex03 Data 7 noiembrie 2018 10:21:36
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
ifstream fin ("ctc.in"); ofstream fout ("ctc.out");

vector <int> adj[MAXN], con, idx, lowlink, in_stack;
vector<vector <int> > C;
stack <int> S;
int index;

void read_in (vector<int>* andj, int &n)
{
    int cnt_edges, x, y;
    fin >> n;
    for (fin >> cnt_edges; cnt_edges > 0; --cnt_edges)
        fin >> x >> y, adj[x - 1].push_back(y - 1);
    fin.close();
}

void print_out (const vector < vector <int> >& G)
{
    fout << G.size() << '\n';
    for (size_t i = 0; i < G.size(); i++)
    {
        for (size_t j = 0; j < G[i].size(); j++)
            fout << G[i][j] + 1 << ' ';
        fout << '\n';
    }
}

void tarjan (const int n, const vector <int>* adj)
{
    idx[n] = lowlink[n] = index;
    index++;
    S.push(n), in_stack[n] = 1;

    vector <int>::const_iterator it;
    for (it = adj[n].begin(); it!=adj[n].end(); ++ it)
    {
        if (idx[*it] == -1) tarjan(*it, adj), lowlink[n] = min (lowlink[n], lowlink[*it]);
        else if (in_stack[*it]) lowlink[n] = min (lowlink[n], lowlink[*it]);
    }
    if (idx[n] == lowlink[n])
    {
        con.clear();
        int node;
        do
        {
            con.push_back(node = S.top());
            S.pop(), in_stack[node] = 0;
        }
        while (node != n);
        C.push_back(con);
    }
}

int main ()
{
    int n;
    read_in(adj, n);

    idx.resize(n), lowlink.resize(n), in_stack.resize(n);
    idx.assign (n, -1), in_stack.assign(n, 0);
    for (int i = 0; i < n; i++) if (idx[i] == -1)
        tarjan(i, adj);
    print_out(C);
    return 0;
}