Cod sursa(job #3270174)

Utilizator cris71Vlad Bogdan Cristian cris71 Data 22 ianuarie 2025 12:44:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int const lmax=100007;
vector<int>G[lmax];
vector<int>GT[lmax];
int n,m,nrc;
bool viz[lmax];
int post[lmax],ind=1;
vector <int>ctc[lmax];///ctc[i]=lista cu muchiile din ctc i
void citire()
{
    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);
    }
}
void dfs1(int node)
{
    viz[node]=true;
    for(auto vec:G[node])
    {
        if(viz[vec]==0)
        {
            dfs1(vec);
        }
    }
    post[ind++]=node;
}
void dfs2(int node)
{
    viz[node]=false;
    ctc[nrc].push_back(node);
    for(auto vec:GT[node])
    {
        if(viz[vec]==1)
        {
            dfs2(vec);
        }
    }

}
int main()
{
    citire();
    ///incep dfs
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==false)
        {
            dfs1(i);
        }
    }
    ///acum fac dfs in post de la n la 1, tine cont de viz care acum e invers
    for(int i=n;i>=1;i--)
    {
        if(viz[post[i]]!=false)
        {
            nrc++;
            dfs2(post[i]);
        }
    }
    fout<<nrc<<"\n";
    for(int i=1;i<=nrc;i++)
    {
        for(auto j:ctc[i])
        {
            fout<<j<<" ";
        }
        fout<<"\n";
    }
    return 0;
}