Pagini recente » Cod sursa (job #2165487) | Cod sursa (job #746854) | Cod sursa (job #2376697) | Cod sursa (job #2566615) | Cod sursa (job #3264735)
#include <fstream>
#include <list>
#include <bitset>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
#define VISITED 1
#define UNVISITED 0
list<int> adj[100001];
bitset<100001> vis;
void writeGraph(const int& n)
{
for(int i=1; i<=n; i++)
{
cout<<i<<": ";
if(!adj[i].empty())
for(auto e: adj[i])
cout<<e<<" ";
cout<<"\n";
}
}
void readGraph(const int& m)
{
int n1, n2;
for(int i=0; i<m; i++)
{
cin>>n1>>n2;
adj[n1].push_back(n2);
adj[n2].push_back(n1);
}
}
void dfs(int node)
{
vis[node]=VISITED;
if(!adj[node].empty())
{
for(int n: adj[node])
{
if(vis[n]==UNVISITED)
dfs(n);
}
}
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin>>n>>m;
readGraph(m);
//writeGraph(n);
int CC=0;
for(int i=1 ; i<=n; i++)
{
if(vis[i]==UNVISITED)
{
CC++;
dfs(i);
}
}
cout<<CC;
}