Cod sursa(job #2789857)

Utilizator etienAndrone Stefan etien Data 28 octombrie 2021 01:38:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>v[100001],vt[100001];
int viz[100001],Viz[100001],j;
stack<int>st;
vector<vector<int>>ctc;
vector<int>cc;
void dfs(int nod)
{
    viz[nod]=true;
    for(auto q:v[nod])
    {
        if(!viz[q])
            dfs(q);
    }
    st.push(nod);
}
void Dfs(int nod)
{
    Viz[nod]=true;
    for(auto q:vt[nod])
    {
        if(!Viz[q])
            Dfs(q);
    }
    cc.push_back(nod);
}
int main()
{
    int n,m,i,a,b;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        vt[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    while(!st.empty())
    {
        j=st.top();
        st.pop();
        if(!Viz[j])
        {
            cc.clear();
            Dfs(j);
            ctc.push_back(cc);
        }
    }
    fout<<ctc.size()<<"\n";
    for(auto q:ctc)
    {
        for(auto q2:q)
            fout<<q2<<" ";
        fout<<"\n";
    }
}