Pagini recente » Cod sursa (job #84483) | Cod sursa (job #1171429) | Cod sursa (job #2036369) | Cod sursa (job #2607660) | Cod sursa (job #1430449)
#include <fstream>
#include <vector>
#define NMax 100010
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector<int> G[NMax];
int nodes, edges, conxcom, n1, n2, top;
bool mark[NMax];
struct mstack
{
int node;
int indx;
}st[NMax];
void dfs(int stnode) {
st[++top].node = stnode;
st[top].indx = 0;
mark[stnode] = 1;
while (top > 0) {
while (st[top].indx == G[st[top].node].size() && top > 0)
top--;
if (top == 0)
break;
if (!mark[G[st[top].node][st[top].indx]]) {
st[++top].node = G[st[top - 1].node][st[top - 1].indx];
st[top].indx = 0;
mark[st[top].node] = 1;
st[top - 1].indx++;
}
else
st[top].indx++;
}
}
int main()
{
f >> nodes >> edges;
for (int i = 1; i <= edges; i++) {
f >> n1 >> n2;
G[n1].push_back(n2);
G[n2].push_back(n1);
}
for (int i = 1; i <= nodes; i++) {
if (!mark[i]) {
top = 0;
conxcom++;
dfs(i);
}
}
g << conxcom;
return 0;
}