Cod sursa(job #3296211)

Utilizator andrei.nNemtisor Andrei andrei.n Data 12 mai 2025 10:10:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define int int64_t

using namespace std;

const int NMAX = 100005;

vector<int> v[NMAX];
vector<int> t[NMAX];
vector<int> ord;
int nr;
vector<int> comp[NMAX];
bitset<NMAX> visited;

void dfs(int source, bool isT)
{
    visited[source] = 1;
    if(isT)
    {
        comp[nr].push_back(source);
        for(const auto &node : t[source])
            if(!visited[node])
                dfs(node, true);
    }
    else
    {
        for(const auto &node : v[source])
            if(!visited[node])
                dfs(node, false);
        ord.push_back(source);
    }
}

signed main()
{
    ifstream fin ("ctc.in");
    ofstream fout ("ctc.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n,m; fin>>n>>m;
    for(int i=0; i<m; ++i)
    {
        int x,y; fin>>x>>y;
        v[x].push_back(y);
        t[y].push_back(x);
    }
    for(int i=1; i<=n; ++i)
        if(!visited[i])
            dfs(i, false);
    visited.reset();
    for(int i=n-1; i>=0; --i)
        if(!visited[ord[i]])
        {
            ++nr;
            dfs(ord[i], true);
        }
    fout<<nr<<'\n';
    for(int i=1; i<=nr; ++i, fout<<'\n')
        for(auto &j : comp[i])
            fout<<j<<' ';
    return 0;
}