Pagini recente » Cod sursa (job #3242455) | Cod sursa (job #1427460) | Cod sursa (job #294208) | Cod sursa (job #853132) | Cod sursa (job #1166346)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100009
#define pb push_back
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int N,M,sol,x,y,k;
vector < int > G[Nmax];
int comp[Nmax],st[Nmax];
inline void GetCC(int S)
{
for( st[++k]=S; k;)
{
int node = st[k--];
comp[node]=sol;
while(G[node].size()>0)
{
int fiu=G[node].back();
if(!comp[fiu])comp[fiu]=sol , st[++k]=fiu;
G[node].pop_back();
G[fiu].erase(find(G[fiu].begin(),G[fiu].end(),node));
}
}
}
int main()
{
f>>N>>M;
for (int i=1; i<=M; ++i)
f>>x>>y , G[x].pb(y) , G[y].pb(x);
for (int i=1; i<=N; ++i)
if (!comp[i])
++sol , GetCC(i);
g<<sol<<'\n';
f.close(); g.close();
return 0;
}