Pagini recente » Cod sursa (job #80119) | Monitorul de evaluare | Cod sursa (job #1641424) | Cod sursa (job #1664406) | Cod sursa (job #1267930)
#include <fstream>
#include <list>
#include <stack>
using namespace std;
list <int> adiacList[100001];
char isVisited[100001];
int main()
{
FILE * fin = fopen("dfs.in", "r");
FILE * fout = fopen("dfs.out", "w");
int m, n, i, j, x;
fscanf(fin, "%d %d", &n, &m);
while(m--)
{
fscanf(fin, "%d %d", &i, &j);
adiacList[i].push_back(j);
adiacList[j].push_back(i);
}
stack<int> st;
list<int>::iterator it, it_end;
for (x = 1, i = 0; x <= n; ++x)
{
if (!isVisited[x])
{
++i;
isVisited[x] = 1;
st.push(x);
while (!st.empty())
{
j = st.top();
st.pop();
for (it = adiacList[j].begin(), it_end = adiacList[j].end(); it != it_end; ++it)
{
if (!isVisited[*it])
{
isVisited[*it] = i;
st.push(*it);
}
}
}
}
}
fprintf(fout, "%d\n", i);
fclose(fin);
fclose(fout);
return 0;
}