Mai intai trebuie sa te autentifici.
Cod sursa(job #966816)
| Utilizator | Data | 26 iunie 2013 16:47:09 | |
|---|---|---|---|
| Problema | Parcurgere DFS - componente conexe | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.92 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
int N, M;
vector <vector <int>> graph;
vector <bool> visited;
ifstream in ("dfs.in");
ofstream out ("dfs.out");
void load ()
{
in >> N >> M;
graph.resize(N);
visited.resize(N, false);
for (int i = 0; i < M; i++)
{
int a, b;
in >> a >> b;
graph[a-1].push_back (b-1);
}
}
void dfs (int start)
{
stack<int> st;
st.push (start);
visited[start] = true;
while (!st.empty())
{
int node = st.top();
st.pop();
for (int i = 0; i < graph[node].size(); i++)
{
visited[graph[node][i]] = true;
st.push(graph[node][i]);
}
}
}
int countConexComp ()
{
int count = 0;
for (int i = 0; i < N; i++)
if (!visited[i])
{
dfs(i);
count ++;
}
}
int main ()
{
out << countConexComp () << endl;
return 0;
}
