Cod sursa(job #3272622)

Utilizator catalin-4Pasca Catalin catalin-4 Data 30 ianuarie 2025 12:51:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n,nrc=0,viz[501101],m,t[2][501101],start[501001],i,j,k=0;
void DF(int x)
{
    int p;
    p=start[x];
    viz[x]=nrc;
   while (p)
   {
       if(viz[t[0][p]]==0)
        DF(t[0][p]);
       p=t[1][p];
   }
}
int main()
{
    in>>n>>m;
    for(int y=1;y<=m;y++)
    {
        in>>i>>j;
        k++;
        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(int y=1;y<=n;y++)
    {
        if(viz[y]==0)
        {
            nrc++;
            DF(y);
        }
    }
    out<<nrc<<'\n';
    return 0;
}