Cod sursa(job #3324767)

Utilizator vladneaguVladneagu vladneagu Data 23 noiembrie 2025 13:49:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
int n,m;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int> adj[maxn];
vector<int> revadj[maxn];
vector<int> topor;
vector<int> rsp[maxn];
bool viz[maxn];
int coun[maxn];
void dfs1(int nod) {
    viz[nod]=1;
    for (auto elem:adj[nod]) {
        if (!viz[elem])dfs1(elem);
    }
    topor.push_back(nod);
}
void dfs2(int nod,int cnt) {
    viz[nod]=1;
    coun[nod]=cnt;
    rsp[cnt].push_back(nod);
    for (auto elem:revadj[nod]) {
        if (!viz[elem])dfs2(elem,cnt);
    }
}
void solve() {
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int l,r;
        cin>>l>>r;
        adj[l].push_back(r);
        revadj[r].push_back(l);
    }
    for (int i=1;i<=n;i++) {
        if (!viz[i]) {
            dfs1(i);
        }
    }
    reverse(topor.begin(),topor.end());
    for (int i=1;i<=n;i++) {
        viz[i]=false;
    }
    int cnt=0;
    for (auto elem:topor) {
        if (!viz[elem]) {
            cnt++;
            dfs2(elem,cnt);
        }
    }
    for (int i=1;i<=n;i++) {
        viz[i]=false;
    }
    cout<<cnt<<endl;
    for (int i=1;i<=cnt;i++) {
        sort(rsp[i].begin(),rsp[i].end());
    }
    for (int elem=1;elem<=n;elem++) {
        if (!viz[elem]) {
            int cntx=coun[elem];
            //cout<<rsp[cntx].size()<<" ";
            for (auto x:rsp[cntx]) {
                cout<<x<<" ";
                viz[x]=true;
            }
            cout<<'\n';
        }
    }
}
signed main()
{
    int t;
    t=1;
    while(t--)solve();
    return 0;
}