Pagini recente » Cod sursa (job #2309090) | Cod sursa (job #866421) | Cod sursa (job #282321) | Cod sursa (job #92785) | Cod sursa (job #1651892)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdio>
#include <stack>
#define DimMax 100100
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m;
vector <bool> viz;
vector < vector<int> > L;
int Componente_Conexe(int noduri);
int DFS(int k);
void Citire();
void DFS_it(int k);
void Citire()
{
int x,y,i;
fin>>n>>m;
L.resize(n);
viz.resize(n,false);
for(i=1;i<=m;i++)
{
fin>>x>>y;
x--;
y--;
L[x].push_back(y);
L[y].push_back(x);
///cout<<x<<" "<<y<<"\n";
}
///cout<<n<<"dfgfe"<<m<<"\n";
}
int Componente_Conexe(int noduri)
{
int i,cnt=0;
for(i=0;i<noduri;i++)
if(viz[i]==false)
{
DFS(i);
cnt++;
}
return cnt;
}
int DFS(int k)
{
int i;
viz[k]=true;
for(i=0;i<L[k].size();i++)
{
if(viz[L[k][i]]==false)
{
viz[L[k][i]]=true;
DFS(i);
}
}
}
void DFS_it(int k) {
if (k < 0 || k > n - 1) {
return;
}
stack<int> s;
int i;
s.push(k);
viz[k] = true;
while (!s.empty()) {
int element = s.top();
bool found = false;
for (i = 0; i < L[element].size() && !found; i++) {
if (!viz[L[element][i]]) {
found = true;
}
}
if (found) {
i--;
s.push(L[element][i]);
viz[L[element][i]] = true;
} else {
s.pop();
}
}
}
int main()
{
Citire();
fout<<Componente_Conexe(n);
return 0;
}