Pagini recente » Cod sursa (job #1945539) | Cod sursa (job #2290233) | Cod sursa (job #2649119) | Cod sursa (job #1791734) | Cod sursa (job #966819)
Cod sursa(job #966819)
#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 ++;
}
return count;
}
int main ()
{
out << countConexComp () << endl;
return 0;
}