Cod sursa(job #3215530)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 15 martie 2024 09:31:39
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<unordered_map>
#include<map>
#include<unordered_set>
#include<ctime>
#include<random>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ld = long double;

mt19937 rng(time(nullptr));

constexpr int NMAX = 1e5 + 1;

vector<int> g[2][NMAX]; bool viz[NMAX];

void dfs(int v, int id, vector<int> &u)
{
    viz[v] = 1; u.eb(v);
    for(auto &it : g[id][v])
        {
            if(!viz[it])
                dfs(it,id,u);
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    int n,m,a,b; cin >> n >> m;
    for(int i = 0 ; i < m ; i++)
        {
            cin >> a >> b;
            g[0][a].eb(b);
            g[1][b].eb(a);
        }

    vector<int> o;
    for(int i = 1; i <= n ; i++)
        if(!viz[i]) dfs(i,0,o);
    reverse(o.begin(),o.end()); memset(viz,0,sizeof(viz));

    vector<vector<int>> comps;
    for(auto &v : o)
        {
            if(viz[v]) continue;
            vector<int> comp; dfs(v,1,comp);
            comps.pb(comp);
        }

    cout << comps.size() << '\n';
    for(int i = 0 ; i < comps.size() ; i++, cout << '\n')
        {
            sort(comps[i].begin(),comps[i].end());
            for(auto &it : comps[i])
                cout << it << " ";
        }
}