Pagini recente » Cod sursa (job #3178568) | Cod sursa (job #960737) | Cod sursa (job #180970) | Cod sursa (job #3172209) | Cod sursa (job #1235210)
#include <cstdio>
#include <vector>
using namespace std;
const char InFile[]="dfs.in";
const char OutFile[]="dfs.out";
class Graph
{
int v;
vector<int> *adj;
int cnt;
void DFSutil(int v,bool *visited);
public:
Graph(int v);
void addEdge(int v,int w);
void DFS();
int CNT();
};
Graph::Graph(int v)
{
this->v=v;
adj=new vector<int>[v];
cnt=0;
}
void Graph::addEdge(int v,int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
void Graph::DFSutil(int v,bool *visited)
{
visited[v]=1;
vector<int>::iterator it;
for(it=adj[v].begin();it!=adj[v].end();++it)
if(!visited[*it])
DFSutil(*it,visited);
}
void Graph::DFS()
{
bool visited[v];
for(int i=1;i<v;++i)
visited[i]=false;
for(int i=1;i<v;++i)
if(!visited[i])
{
++cnt;
DFSutil(i,visited);
}
}
int Graph::CNT()
{
return cnt;
}
int main()
{
int a,b,n,m;
freopen(InFile,"r",stdin);
freopen(OutFile,"w",stdout);
scanf("%d %d",&n,&m);
Graph g(n+1);
for(int i=1;i<=m;++i)
{
scanf("%d %d",&a,&b);
g.addEdge(a,b);
}
g.DFS();
printf("%d\n",g.CNT());
return 0;
}