Cod sursa(job #2534214)

Utilizator lucianul31Moisii Lucian lucianul31 Data 30 ianuarie 2020 11:22:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include<bits/stdc++.h>

using namespace std;

const char iname[] = "ctc.in";
const char oname[] = "ctc.out";

#define MAXN  100005
#define Min(a, b)  ((a) < (b) ? (a) : (b))
vector <int> adj[MAXN], con, idx, low, in_stack;
vector < vector <int> > C;
stack <int> S;
int indecs;

void read_in(vector <int>* adj, int& n, const char iname[])

{
    ifstream in(iname);
    int cnt_edges, x, y;
    in >> n;
    for (in >> cnt_edges; cnt_edges > 0; -- cnt_edges)
        in >> x >> y,
        adj[x - 1].push_back(y - 1);
    in.close();
}

void print_out(const vector < vector <int> >& G, const char oname[])
{
    ofstream out(oname);
    out << G.size() << "\n";
    for (size_t i = 0; i < G.size(); ++ i)
    {
        for (size_t j = 0; j < G[i].size(); ++ j)
            out << G[i][j] + 1 << " ";
        out << "\n";
    }
    out.close();
}

void tarjan(const int n, const vector <int>* adj)

{
    idx[n] = low[n] = indecs;
    indecs ++;
    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),
                   low[n] = Min(low[n], low[*it]);
        else if (in_stack[*it])
            low[n] = Min(low[n], low[*it]);
    }
    if (idx[n] == low[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(void)

{
    int n;
    read_in(adj, n, iname);
    idx.resize(n), low.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, oname);
    return 0;

}