Cod sursa(job #3344946)

Utilizator SimifilLavrente Simion Simifil Data 6 martie 2026 21:28:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int maxn = 1e5+1;
vector<int> graph[maxn], Tgraph[maxn], edge[maxn];
vector<int> topsort, fr(maxn);
int n, m;

void dfs( int node )
{
    fr[node] = 1;
    for( auto adj : graph[node] )
    {
        if( fr[adj] == 0 )
        {
            dfs(adj);
        }
    }
    topsort.push_back(node);
}

vector<int> component;

void dfs2( int node )
{
    fr[node] = 1;
    component.push_back(node);
    for( auto adj : Tgraph[node] )
    {
        if( fr[adj] == 0 )
        {
            dfs2(adj);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);f.tie(nullptr);g.tie(nullptr);
    f >> n >> m;
    for( int i = 1; i <= n; ++i )
        fr[i] = 0;
    for( int i = 1; i <= m; ++i )
    {
        int a, b;
        f >> a >> b;
        graph[a].push_back(b);
        Tgraph[b].push_back(a);
    }
    for( int i = 1; i <= n; ++i )
    {
        if( fr[i] == 0 )
            dfs(i);
    }
    for( int i = 1; i <= n; ++i )
        fr[i] = 0;
    vector<vector<int>> ans;
    int cnt = -1;
    for( int i = topsort.size()-1; i >= 0; --i )
    {
        int node = topsort[i];
        if( fr[node] == 0 )
        {
            ++cnt;
            ans.push_back({});
            component.clear();
            dfs2(node);
            for( int j = 0; j < component.size(); ++j )
            {
                ans[cnt].push_back( component[j] );
            }
        }
    }
    g << ans.size() << "\n";
    for( int i = 0; i < ans.size(); ++i )
    {
        for( auto j : ans[i] )
            g << j << " ";
        g << "\n";
    }
    return 0;
}