Cod sursa(job #2788721)

Utilizator luciabianca24Tudorache Lucia Bianca luciabianca24 Data 26 octombrie 2021 12:37:23
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;
int n;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>viz;
vector<vector<int>>g,gt,sol;
stack<int>s;
void citire()
{
    int i1,i2,m;
    fin>>n>>m;
    g=gt=sol=vector<vector<int>>(n+1);
    viz=vector<int>(n+1);
    for(int i=1; i<=m; i++)
    {
        fin>>i1>>i2;
        g[i1].push_back(i2);
        gt[i2].push_back(i1);
    }
}
void dfs(int np)
{
    viz[np]=1;
    for(auto e:g[np])
        if(!viz[e])
            dfs(e);
    s.push(np);
}
void dfst(int np,int cnt)
{
    viz[np]=cnt;
    sol[cnt].push_back(np);
    for(auto e:gt[np])
        if(!viz[e])
            dfst(e,cnt);
}
int main()
{
    citire();
    for(int i=1; i<=n; i++)
        if(!viz[i])
            dfs(i);
    for(int i=1; i<=n; i++)
        viz[i]=0;
    int vf,nrct=0;
    while(!s.empty())
    {
        vf=s.top();
        if(!viz[vf])
        {
            nrct++;
            dfst(vf,nrct);
        }
        s.pop();
    }
    for(int i=1;i<=n;i++)
        sort(sol[i].begin(),sol[i].end());
    fout<<nrct<<'\n';
    for(int i=1;i<=nrct;i++,cout<<'\n')
        for(auto e:sol[i])
        fout<<e<<' ';
}