Pagini recente » Cod sursa (job #2750746) | Cod sursa (job #1751784) | Cod sursa (job #841745) | Cod sursa (job #2058375) | Cod sursa (job #2085549)
#include <fstream>
#include <vector>
#include <stack>
#define MaxN 100001
using namespace std;
int N, M, x, y, comp=0, z;
vector<int> AdList[MaxN];
bool viz[MaxN];
void Read()
{
ifstream f("dfs.in");
f>>N>>M;
for (int i=1;i<=N;i++)
AdList[i].push_back(0);
for (int i=0;i<M;i++)
{
f>>x>>y;
AdList[x].push_back(y);
AdList[x][0]++;
AdList[y].push_back(x);
AdList[y][0]++;
}
}
void DFS(int a)
{
stack<int> S;
int i;
S.push(a);
while (!S.empty())
{
z=S.top();
i=1;
while (i<=AdList[z][0] && viz[AdList[z][i]])
i++;
if (i!=AdList[z][0]+1)
{
S.push(AdList[z][i]);
viz[AdList[z][i]]=1;
}
S.pop();
}
comp++;
}
int main()
{
Read();
for (int i=1;i<=N;i++)
if (!viz[i])
DFS(i);
ofstream g("dfs.out");
g<<comp;
}