Cod sursa(job #3203509)

Utilizator dragosdragonnIosub Dragos Casian dragosdragonn Data 13 februarie 2024 19:57:52
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAX 200005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int nr;
vector <int> G[MAX];
vector <int> GT[MAX];
vector <int> stocare[MAX];
bool vizg[MAX];
bool vizgt[MAX];
bool viz[MAX];
int n,m;
void citire()
{
    fin>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}
void dfsg(int nod)
{
    vizg[nod]=1;
    for(size_t i=0;i<G[nod].size();i++)
    {
        if(!vizg[G[nod][i]])
        dfsg(G[nod][i]);
    }
}
void dfsgt(int nod)
{
    vizgt[nod]=1;
    for(size_t i=0;i<GT[nod].size();i++)
    {
        if(!vizgt[GT[nod][i]])
        dfsgt(GT[nod][i]);
    }
}
void detcomp()
{
    nr++;
    for(int i=1;i<=n;i++)
    {
        if(vizg[i]==vizgt[i] && vizg[i]==1)
        {
            stocare[nr].push_back(i);
            viz[i]=1;
        }
    }
}
void demnoduri()
{
    for(int i=1;i<=n;i++)
    {
        vizg[i]=vizgt[i]=0;
    }
}
void plusminus()
{
   for(int i=1;i<=n;i++)
   {
       if(!viz[i])
       {
           dfsg(i);
           dfsgt(i);
           detcomp();
           demnoduri();
       }
   }
}
void afisare()
{
    fout<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        for(size_t j=0;j<stocare[i].size();j++)
        {
            fout<<stocare[i][j]<<" ";
        }
        fout<<'\n';
    }
}
int main()
{
    citire();
    plusminus();
    afisare();
    return 0;
}