Cod sursa(job #2925482)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 15 octombrie 2022 13:51:08
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

vector <int> l[100001], v(100001), mn(100001), curent(100001), ctc[100001];
stack <int> st;
int n, id = 0, nrc = 0;

void df (int vf)
{
    st.push(vf);
    curent[vf] = 1;
    v[vf] = mn[vf] = ++id;
    for (int i = 0; i < l[vf].size(); i++)
    {
        if (!v[l[vf][i]])
            df(l[vf][i]);
        if (curent[l[vf][i]])
            mn[vf] = min(mn[vf], mn[l[vf][i]]);
    }
    if (v[vf] == mn[vf])
    {
        ctc[nrc].push_back(vf);
        int x = st.top();
        st.pop();
        while (x != vf)
        {
            curent[x] = 0;
            mn[x] = v[vf];
            ctc[nrc].push_back(x);
            x = st.top();
            st.pop();
        }
        nrc++;
    }
}

void tarjan()
{
    for (int i = 1; i <= n; i++)
        if (!v[i])
            df(i);
}

int main()
{int m, x, y, i, j;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
f >> n >> m;
for (i = 1; i <= m; i++)
{
    f >> x >> y;
    l[x].push_back(y);
}
tarjan();
g << nrc << '\n';
for (i = 0; i < nrc; i++)
{
    for (j = 0; j < ctc[i].size(); j++)
        g << ctc[i][j] << ' ';
    g << '\n';
}
return 0;
}