Cod sursa(job #2701968)

Utilizator enedumitruene dumitru enedumitru Data 2 februarie 2021 14:48:04
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m,a,b,c;
int f1[100001],f2[100001],ctc[100001];
vector <int> graf[100001],invers[100001],componente[100001];
void ctcf(int a)
{
    f1[a]=c;
    for(int i=0;i<graf[a].size();i++)
    {
        if(f1[graf[a][i]]!=c&&ctc[graf[a][i]]==0)
        {
            ctcf(graf[a][i]);
        }
    }
}
void ctcinv(int a)
{
    ctc[a]=1;
    componente[c].push_back(a);
    f2[a]=c;
    for(int i=0;i<invers[a].size();i++)
    {
        if(f2[invers[a][i]]!=c&&f1[invers[a][i]]==c)
        {
            ctcinv(invers[a][i]);
        }
    }

}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        graf[a].push_back(b);
        invers[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(ctc[i]==0)
        {
            c++;
            ctcf(i);
            ctcinv(i);
        }
    }
    cout<<c<<'\n';
    for(int i=1;i<=c;i++)
    {
        for(int j=0;j<componente[i].size();j++)
        {
            cout<<componente[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}