Cod sursa(job #3277325)

Utilizator BogdanBurescuBogdan Burescu BogdanBurescu Data 15 februarie 2025 18:58:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

ifstream cin ("ctc.in");
ofstream cout ("ctc.out");

int t,m,c,u,v,curr,vec,x,y,ok,mask,cost,maxi,nr0,nr1,a[300005],b,poz,n,k,i,j,l,r,mij,mini,p,nr,sum,mod=1e9+7;
//string s[1005];
vector<int>g[200005],gt[200005];
queue<int>q;
vector<int>s;
vector<int>vis;
vector<int>ans[200005];

void dfs(int k)
{
    vis[k]=1;
    for(auto x:g[k])
        if(!vis[x])
            dfs(x);
    s.push_back(k);
}

void dfsgt(int k)
{
    vis[k]=1;
    ans[nr].push_back(k);
    for(auto x:gt[k])
        if(!vis[x])
            dfsgt(x);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>u>>v;
        g[u].push_back(v);
        gt[v].push_back(u);
    }
    vis=vector<int>(n+5,0);
    for(i=1; i<=n; i++)
        if(!vis[i])
            dfs(i);

    vis=vector<int>(n+5,0);
    for(auto it=s.rbegin(); it!=s.rend(); it++)
        if(!vis[*it])
        {
            nr++;
            dfsgt(*it);
        }
    cout<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        sort(ans[i].begin(),ans[i].end());
        for(auto x:ans[i])
            cout<<x<<' ';
        cout<<'\n';
    }
    return 0;
}