Cod sursa(job #3289456)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 26 martie 2025 22:45:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 1;
vector<int> vec[NMAX], trans[NMAX];
bool vis[NMAX];
vector<vector<int>> comps;
vector<int> stk;

void dfs1(int nod)
{
    vis[nod] = 1;
    for(auto i : vec[nod])
        if(!vis[i])
            dfs1(i);
    stk.push_back(nod);
}

void dfs2(int nod, vector<int>& comp)
{
    vis[nod] = 1;
    comp.push_back(nod);
    for(auto i : trans[nod])
        if(!vis[i])
            dfs2(i, comp);
}

int main()
{
    int n, m;
    fin >> n >> m;
    while(m--)
    {
        int i, j;
        fin >> i >> j;
        vec[i].push_back(j);
        trans[j].push_back(i);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
            dfs1(i);
    }
    memset(vis, 0, sizeof(vis));
    reverse(stk.begin(), stk.end());
    for(auto nod : stk)
    {
        if(!vis[nod])
        {
            vector<int> comp;
            dfs2(nod, comp);
            comps.push_back(comp);
        }
    }
    fout << comps.size() << '\n';
    for(auto comp : comps)
    {
        for(auto nod : comp)
            fout << nod << ' ';
        fout << '\n';
    }

    return 0;
}