Cod sursa(job #2978248)

Utilizator AffectiveSmile2Mihnea Matea AffectiveSmile2 Data 13 februarie 2023 15:49:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX=100001;
int N,M,post[NMAX],nr,nrc;///nr = indice in post
///in post apar toate nodurile in ordinea timpilor de finalizare
bool viz[NMAX];
struct nod
{
    int x;
    nod *next;
};
nod *G[NMAX],*GT[NMAX],*CTC[NMAX];///graf,graf transpus, lista nodurilor din a i-a comp tare conexa
void add(nod *&cap_lst,int nod_ad)
{
    nod *p;
    p=new nod;
    p->x=nod_ad;
    p->next=cap_lst;
    cap_lst=p;
}
void citiregraf()
{
    int x,y;
    f>>N>>M;
    while(M--)
    {
        f>>x>>y;
        add(G[x],y);
        add(GT[y],x);
    }
}
void DFS(int vf)
{
    viz[vf]=1;
    for(nod *p=G[vf];p!=NULL;p=p->next)
        if(!viz[p->x])
            DFS(p->x);
    post[++nr]=vf;
}
void DFSt(int vf)
{
    viz[vf]=0;
    add(CTC[nrc],vf);
    for(nod *p=GT[vf];p!=NULL;p=p->next)
        if(viz[p->x])
            DFSt(p->x);
}
void componente()
{
    int i;
    for(i=1;i<=N;i++)
        if(!viz[i])
            DFS(i);
    for(i=N;i>0;i--)
        if(viz[post[i]]==1)
    {
        nrc++;
        DFSt(post[i]);
    }
}
void afis()
{
    g<<nrc<<'\n';
    for(int i=1;i<=nrc;i++)
    {
        for(nod *p=CTC[i];p!=NULL;p=p->next)
            g<<p->x<<' ';
        g<<'\n';
    }
}
int main()
{
    citiregraf();
    componente();
    afis();
    f.close();
    g.close();
    return 0;

}