Mai intai trebuie sa te autentifici.
Cod sursa(job #2103534)
| Utilizator | Data | 10 ianuarie 2018 14:22:53 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.98 kb |
#include <bits/stdc++.h>
using namespace std;
int vertices, edges, u, v, conexParts;
vector<int> adj[100001];
bool visited[100001];
void DFS(int start)
{
stack<int> s;
s.push(start);
while(!s.empty())
{
int current = s.top(); s.pop();
if(visited[current] == false)
{
for(int child : adj[current])
{
s.push(child);
}
visited[current] = true;
}
}
}
int main(){
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &vertices, &edges);
for(int i = 1; i <= edges; i++)
{
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1; i <= vertices; i++)
{
if(visited[i] == false)
{
DFS(i);
conexParts++;
}
}
printf("%d", conexParts);
return 0;
}
