Cod sursa(job #2979989)

Utilizator andrein2005Andrei Stefan Neacsu andrein2005 Data 16 februarie 2023 09:44:57
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include    <iostream>
#include    <fstream>
#include    <vector>
#include    <set>

#define N 100001

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector <int> Graf[N],GrafT[N];
int n,m,nrctc,u[N],CTC[N];
set <int> S1,S2;


void empty ()
{
    for (int i=1; i<=n; i++) u[i]=0;
}
void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x,y;
        fin >> x >> y;
        Graf[x].push_back(y);
        GrafT[y].push_back(x);
    }
}

void dfsGraf(int x)
{
    u[x]=1;
    S1.insert(x);
    for(int i=0; i<Graf[x].size(); i++)
    {
        int y = Graf[x][i];
        if(!u[y])
            dfsGraf(y);
    }
}
void dfsGrafT(int x)
{
    u[x]=1;
    S2.insert(x);
    for(int i=0; i<GrafT[x].size(); i++)
    {
        int y = GrafT[x][i];
        if(!u[y])
            dfsGrafT(y);
    }
}
void solve()
{
    for(int i=1; i<=n; i++)
        if(!CTC[i])
        {
            S1.clear ();
            S2.clear ();
            nrctc++;
            empty();
            dfsGraf(i);
            empty();
            dfsGrafT(i);
            for (set<int>::iterator it=S1.begin(); it!=S1.end(); ++it)
            {
                if (S2.count(*it)) CTC[*it]=nrctc;

            }
        }
}
void afis()
{
    fout << nrctc <<"\n";
    for (int i=1; i<=nrctc; i++) {
        for (int j=1; j<=n; j++) if (CTC[j]==i) out<<j<<' ';
        out<<'\n';
    }
}
int main()
{
    citire();
    solve();
    afis();
    return 0;
}