Cod sursa(job #2612130)

Utilizator sauron275Andrei Radu sauron275 Data 8 mai 2020 15:20:51
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int NMAX=100000;
struct nod
{
    int x;
    nod *next;
};
nod *G[NMAX+1],
GT[NMAX+1],
CTC[NMAX+1];
int N,M,nr,post[NMAX+1],nrc;
bool viz[NMAX+1];
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()
{
    f>>N>>M;
    while(M--)
    {
        int x,y;
        f>>x>>y;
        add(G[x],y);
        add(G[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(int i=1;i<=N;i++)
        if(viz[i]==0)
        DFS(i);
    //
    for(i=N;i>=1;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();
    return 0;
}