Cod sursa(job #2604708)

Utilizator GRalyGoia Raluca GRaly Data 23 aprilie 2020 12:22:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int t[2][1000005],start[100005],tata[100005];
short int ap[100005];
int k;
void dfs(int j,int tatic)
{
    bool r=false;
    ap[j]=1;
    tata[j]=tatic;
    k=start[j];
    while(t[0][k]!=0)
        if(ap[t[0][k]]==0)
        {
            ap[t[0][k]]=1;
            dfs(t[0][k],j);
            r=true;
            k=t[1][k];
        }
        else
              k=t[1][k];
    if(r==false&&tatic!=0)
        dfs(tatic,tata[tatic]);
}
int main()
{
    int n,m,o,i,j,nr=0;
    fin>>n>>m;
    k=0;
    for(o=1;o<=m;o++)
    {
        k++;
        fin>>i>>j;
        t[0][k]=j;
        t[1][k]=start[i];
        start[i]=k;
        k++;
        t[0][k]=i;
        t[1][k]=start[j];
        start[j]=k;
    }
    for(o=1;o<=n;o++)
        if(ap[o]==0)
        {
            nr++;
            dfs(o,0);
        }
    fout<<nr;
    return 0;
}