Cod sursa(job #3360823)

Utilizator Andrei_GAndreiG Andrei_G Data 16 iulie 2026 23:27:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#define int long long
//#define int short
using namespace std;

const int nmax = 1e5;

int n, m, cnt = 0;
vector<int> adj[nmax + 5], radj[nmax + 5], top, comp[nmax + 5];

void dfstop(vector<int>& vis, int node){
    vis[node] = 1;
    for (auto& neinode : adj[node]){
        if (!vis[neinode]){
            dfstop(vis, neinode);
        }
    }
    top.push_back(node);
}

void topologicalsort(){
    vector<int> vis(n + 1, 0);
    for (int i = 1; i <= n; i++){
        if (!vis[i]){
            dfstop(vis, i);
        }
    }
    reverse(top.begin(), top.end());
}

void dfscomp(vector<int>& vis, int node){
    vis[node] = 1;
    for (auto& neinode : radj[node]){
        if (!vis[neinode]){
            dfscomp(vis, neinode);
        }
    }
    comp[cnt].push_back(node);
}

void componenteconexe(){
    vector<int> vis(n + 1, 0);
    for (int i = 1; i <= n; i++){
        if (!vis[top[i - 1]]){
            cnt++;
            dfscomp(vis, top[i - 1]);
        }
    }
    cout<<cnt<<"\n";
    for (int i = 1; i <= cnt; i++){
        sort(comp[i].begin(), comp[i].end());
        for (auto& j : comp[i]){
            cout<<j<<" ";
        }
        cout<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    cin>>n>>m;
    while (m--){
        int u, v;
        cin>>u>>v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }
    topologicalsort();
    componenteconexe();
}