Cod sursa(job #2668105)

Utilizator marian222200Dimofte Marian marian222200 Data 4 noiembrie 2020 15:00:20
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
#define N 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct nod{
int info;
nod *urm;
};
nod *l1[N];
nod *l2[N];

int n,m,ct;
int viz1[N],viz2[N];
int c[N],cp,cu;

void citire()
{
    int i,x,y;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        nod *p=new nod;
        p->info=y;
        p->urm=l1[x];
        l1[x]=p;

        p=new nod;
        p->info=x;
        p->urm=l2[y];
        l2[y]=p;
    }
}
void dfs1(int i)
{
    viz1[i]=1;
    for(nod *p=l1[i];p!=NULL;p=p->urm)if(viz1[p->info]==0)dfs1(p->info);

    c[++cu]=i;
}
void parc1()
{
    int i;
    for(i=1;i<=n;i++)
    if(viz1[i]==0)dfs1(i);
}
void dfs2(int i)
{
    viz2[i]=1;
    for(nod *p=l2[i];p!=NULL;p=p->urm)if(viz2[p->info]==0)dfs2(p->info);
}
void parc2()
{
    int j;
    cp=1;
    while(cu>0)
    {
        j=c[cu--];
        if(viz2[j]==0)
        {
            ct++;
            dfs2(j);
        }
    }
}
int main()
{
    citire();
    parc1();
    parc2();
    fout<<ct;
    return 0;
}