Cod sursa(job #2898387)

Utilizator vladsipunct5555Butnrau Vlad vladsipunct5555 Data 6 mai 2022 17:18:41
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
vector <int> v[100001];
vector <int> trans[100001];
int n, m;
queue <int> q;
vector <vector <int> > ans;
bool viz[100001];
void dfs (int nod)
{
    viz[nod] = true;
    for (auto vecin:v[nod])
        if (!viz[vecin])
            dfs(vecin);
    q.push(nod);
}
void dfs_tr (int nod, int loc)
{
    viz[nod] = true;
    ans[loc].push_back(nod);
    for (auto vecin:trans[nod])
        if (!viz[vecin])
            dfs_tr(vecin, loc);
}
main ()
{
    in >> n >> m;
    for (int i = 1;i<=m;++i)
    {
        int a, b;
        in >> a >> b;
        v[a].push_back(b);
        trans[b].push_back(a);
    }
    for (int i = 1;i<=n;++i)
        if (!viz[i])
            dfs(i);
    for (int i = 1;i<=n;++i)
        viz[i] = 0;
    int place = 0;
    for (int i = 1;i<=n;++i)
        if (!viz[i])
        {
            vector <int> newx;
            ans.push_back(newx);
            dfs_tr(i, place);
            place++;
        }
    out << ans.size() << '\n';
    for (auto vect:ans)
    {
        for (auto numar:vect)
            out << numar << ' ';
        out << '\n';
    }
    return 0;
}