Cod sursa(job #2810102)

Utilizator luciabianca2405Tudorache Lucia Bianca luciabianca2405 Data 28 noiembrie 2021 14:51:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,nrctc,k,o[100001];
vector<vector<int>>g,gt;
vector<int>ctc[100001];
vector<int>use;
void read()
{
    int m,x,y;
    cin>>n>>m;
    g=gt=vector<vector<int>>(n+1);
    use=vector<int>(n+1);
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}
void dfsp(int np)
{
    use[np]=1;
    for(int v:g[np])
        if(!use[v])
            dfsp(v);
    o[++k]=np;
}
void dfsm(int np)
{
    use[np]=2,ctc[nrctc].push_back(np);
    for(int v:gt[np])
        if(use[v]==1)
            dfsm(v);
}
void solve()
{
    for(int i=1; i<=n; i++)
        if(!use[i])
            dfsp(i);
    for(int i=k; i>=1; i--)
    {
        int nod=o[i];
        if(use[nod]==1)
        {
            nrctc++;
            dfsm(nod);
        }
    }
}
void afisare()
{
    cout<<nrctc<<'\n';
    for(int i=1; i<=nrctc; i++,cout<<'\n')
        for(int e:ctc[i])
            cout<<e<<' ';
}
int main()
{
    read();
    solve();
    afisare();
    return 0;
}