Cod sursa(job #3262278)

Utilizator RaduStoleriuRadu Stoleriu RaduStoleriu Data 9 decembrie 2024 17:18:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#define NMAX 100001
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m;
vector<int> G[NMAX];
vector<int> Gt[NMAX];
int postordine[NMAX];
bool viz[NMAX];
vector<int>ctc[NMAX];
int nrc,poz,i,x,y;
void citire();
void afisare();
void DFS(int x);
void DFST(int x);
int main()
{
    citire();
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0) DFS(i);
    }
    for(i=n;i>=1;i--)
    {
        if(viz[postordine[i]]!=0)
        {
            nrc++;
            DFST(postordine[i]);
        }
    }
    afisare();
    return 0;
}
void citire()
{
    int i;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
}
void DFS(int x)
{
    int i;
    viz[x]=1;
    for(i=0;i<G[x].size();i++)
    {
        if(viz[G[x][i]]==0)
            DFS(G[x][i]);
    }
    postordine[++poz]=x;
}
void DFST(int x)
{
    int i;
    viz[x]=0;
    ctc[nrc].push_back(x);
    for(i=0;i<Gt[x].size();i++)
    {
        if(viz[Gt[x][i]]==1)
            DFST(Gt[x][i]);
    }
}
void afisare()
{
    cout<<nrc<<'\n';
    int i,j;
    for(i=1;i<=nrc;i++)
    {
        for(j=0;j<ctc[i].size();j++)
        {
            cout<<ctc[i][j]<<" ";
        }
        cout<<'\n';
    }
}