Mai intai trebuie sa te autentifici.
Cod sursa(job #2117710)
Utilizator | Data | 29 ianuarie 2018 11:39:41 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.74 kb |
#include <bits/stdc++.h>
using namespace std;
long long n,m,l,r,v[200005],dist = 0,sum = 0,virf = 0,counti = 0;
vector <int> g[200005],p;
void DFS(int nod){
v[nod]=1;
sum += g[nod].size();
for(int i=0;i<g[nod].size();i++)
{
int next=g[nod][i];
if(v[next]==0)
DFS(next);
}
}
int main()
{
ifstream inFile;
ofstream outFile;
inFile.open("dfs.in");
outFile.open("dfs.out");
inFile>>n>>m;
for(int i = 1; i <= m; i++)
{
inFile>>l>>r;
g[l].push_back(r);
g[r].push_back(l);
}
for(int i=1;i<=n;i++)
{
if(v[i]==0)
{
DFS(i);
}
}
outFile<<sum/2;
outFile.close();
}