Cod sursa(job #2896667)

Utilizator tiut_cristianTiut Cristian tiut_cristian Data 30 aprilie 2022 11:01:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

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

int indecs;

void citire(vector<int> *adj, int & n)
{
    ifstream fin("ctc.in");
    int m, x, y;
    fin >> n >> m;
    while(m)
    {
        fin >> x >> y;
        adj[x - 1].push_back(y - 1);
        m--;
    }
}

void afisare(vector<vector<int>> G)
{
    ofstream fout("ctc.out");

    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] = 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),
            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;
    citire(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);
    afisare(C);

    return 0;
}