Cod sursa(job #3376630)

Utilizator TeodorVTeodorV TeodorV Data 18 noiembrie 2026 18:24:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax=100001;
vector<int> v[Nmax],vInv[Nmax];
bitset<Nmax> visited;
vector<int> l;

void dfs1(int node)
{
    visited[node]=1;
    for(int nxtnode : v[node])
    {
        if(visited[nxtnode]) continue;
        dfs1(nxtnode);
    }
    l.push_back(node);
}
void dfs2(int node, vector<int>& ctc)
{
    visited[node]=1;
    ctc.push_back(node);
    for(int nxtnode : vInv[node])
    {
        if(visited[nxtnode]) continue;
        dfs2(nxtnode, ctc);
    }
}

int main()
{
    int n,m;
    fin>>n>>m;
    l.reserve(n);
    for(int i=1; i<=m; i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        vInv[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
    {
        if(visited[i]) continue;
        dfs1(i);
    }
    visited.reset();
    vector<vector<int>> ctcs;
    for(int i=l.size()-1; i>=0; i--)
    {
        if(visited[l[i]]) continue;
        ctcs.push_back(vector<int>());
        dfs2(l[i], ctcs[ctcs.size()-1]);
    }
    fout<<ctcs.size()<<'\n';
    for(int i=0; i<ctcs.size(); i++)
    {
        //sort(ctcs[i].begin(), ctcs[i].end());
        for(int node : ctcs[i])
            fout<<node<<' ';
        fout<<'\n';
    }
    return 0;
}