Cod sursa(job #3213593)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 13 martie 2024 12:02:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

#define ll long long

//#define fin cin
//#define fout cout

using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

vector <int> g[100005], gt[100005];
vector <int> tari_conexe[100005];

stack <int> st;
bool vizg[100005], vizgt[100005];

void dfsg (int nod)
{
    vizg[nod]=1;
    for (int vecin : g[nod]) {
        if (!vizg[vecin]) {
            dfsg(vecin);
        }
    }
    st.push(nod);
}

void dfsgt (int nod, int index)
{
    vizgt[nod]=1;
    for (int vecin : gt[nod]) {
        if (!vizgt[vecin]) {
            dfsgt(vecin, index);
        }
    }
    tari_conexe[index].push_back(nod);
}

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int n, m, x, y;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for (int i=1; i<=n; i++) {
        if (!vizg[i]) {
            dfsg(i);
        }
    }
    int index=0;
    while (!st.empty()) {
        int nod=st.top();
        if (!vizgt[nod]) {
            dfsgt(nod, index++);
        }
        st.pop();
    }
    fout<<index<<'\n';
    for (int i=0; i<index; i++) {
        for (int nod : tari_conexe[i]) {
            fout<<nod<<' ';
        }
        fout<<'\n';
    }
    return 0;
}