Cod sursa(job #2830181)
Utilizator | Goia Darius Goia_Darius | Data | 9 ianuarie 2022 16:48:28 |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 10 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.93 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int Start[100005],T[2][200005],n,m,viz[100005],k;
void Citire()
{
int i,j;
f>>n>>m;
while (f>>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;
}
}
int dfs(int start)
{
int contor=0,c;
for(int i=1;i<=n;i++)
{
if(viz[i]==0)
contor++;
if(viz[i]==0)
{
c=Start[i];
viz[i]=1;
if(T[1][c]!=0)
while(T[1][c]!=0)
{
viz[T[0][c]]=1;
c=T[1][c];
viz[T[0][c]]=1;
}
else viz[T[0][c]]=1;
}
}
return contor;
}
int main()
{
Citire();
g<<dfs(1);
}