Cod sursa(job #3350105)

Utilizator cris71Vlad Bogdan Cristian cris71 Data 5 aprilie 2026 13:00:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int const lmax=1e5+7;
int n,m;
vector<int>G[lmax],GT[lmax];
bool viz1[lmax],viz2[lmax];
vector<int>ctc[lmax];
int nodetoctc[lmax];
int nrcomp=0;
int post[lmax],ipost;
void dfs(int node)
{
    viz1[node]=true;
    for(auto vec:G[node])
    {
        if(viz1[vec]==true)continue;
        dfs(vec);
    }
    post[ipost++]=node;
}
void dfsT(int node)
{
    ctc[nrcomp].push_back(node);
    nodetoctc[node]=nrcomp;
    viz2[node]=true;
    for(auto vec:GT[node])
    {
        if(viz2[vec]==true)continue;
        dfsT(vec);
    }
}
int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        fin>>a>>b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(viz1[i]==false)
        {
            dfs(i);
        }
    }
    for(int i=ipost-1;i>=0;i--)
    {
        if(viz2[post[i]]==false)
        {
            dfsT(post[i]);
            nrcomp++;
        }
    }
    fout<<nrcomp<<"\n";
    for(int i=0;i<nrcomp;i++)
    {
        for(auto node:ctc[i])
        {
            fout<<node<<" ";
        }
        fout<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}