Pagini recente » Cod sursa (job #1653226) | Cod sursa (job #1906110) | Cod sursa (job #1843985) | Cod sursa (job #2235188) | Cod sursa (job #877054)
Cod sursa(job #877054)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int maxn = 100001;
vector<int> vecini[maxn];
int visited[maxn];
int k = 1, n, m;
void dfs(int nod)
{
stack<int> st; st.push(nod);
while (!st.empty())
{
int top = st.top();
st.pop();
visited[top] = k;
for (int i = 0; i < vecini[top].size(); i++) st.push(vecini[top][i]);
}
for (int i = 1; i <= n; i++)
if (visited[i] == 0) { ++k; dfs(i); break; }
}
int main()
{
int x, y, first = 0;
in >> n >> m;
for (int i = 0; i < m; i++)
{
in >> x >> y;
if (first == 0) first = x;
vecini[x].push_back(y);
}
dfs(first);
out << k;
return 0;
}