Cod sursa(job #2842685)

Utilizator razvanalexrotaruRazvan Alexandru Rotaru razvanalexrotaru Data 1 februarie 2022 12:33:44
Problema Componente tare conexe Scor 12
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
vector<int>G1[100004];
vector<int>G2[100004];
vector<int>sol[100004];
int a,b,n,m,i,j,ok[100004],viz1[100004],viz2[100004],cnt;
void BFS1(int k)
{
    vector<int>::iterator i;
    for(i=G1[k].begin();i!=G1[k].end();i++)
    {
        if(viz1[*i]==0)
        {
            viz1[*i]=1;
            BFS1(*i);
        }
    }
}
void BFS2(int k)
{
    vector<int>::iterator i;
     for(i=G2[k].begin();i!=G2[k].end();i++)
    {
        if(viz2[*i]==0)
        {
            viz2[*i]=1;
            BFS2(*i);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b;
        G1[a].push_back(b);
        G2[b].push_back(a);
    }
    for(i=1;i<=n;i++)
    {
        if(ok[i]==0)
        {
            BFS1(i);
            BFS2(i);
            cnt++;
        }
        for(j=1;j<=n;j++)
        {
            if(viz1[j]==1 && viz2[j]==1)
            {
                ok[j]=1;
                sol[cnt].push_back(j);
            }
            viz1[j]=0;
            viz2[j]=0;
        }
    }
    vector<int>::iterator l;
    cout<<cnt;
    for(i=1;i<=cnt;i++)
    {
        cout<<'\n';
        for(l=sol[i].begin();l!=sol[i].end();l++)
            cout<<*l<<" ";
    }
    return 0;
}