Cod sursa(job #2792664)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 2 noiembrie 2021 09:52:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define ll long long
#define forq(i,ii,n)for(i=ii;i<n;i++)
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n,m,s,i,j,b[100001],l,u,k,t[100001];vector<int>a[100001];bitset<1000001> c;
int main()
{
fill(t,t+100001,-1);
in>>n>>m;
while(m--)in>>i>>j,a[i].push_back(j),a[j].push_back(i);
for(i=1;i<=n;i++)
{
if(c[i]==0)
{
    b[++l]=i,c[i]=1,++s,u=k=l;
       while(u<=l)
{
    while(u<=k)
    {
        for(auto i=a[b[u]].begin();i!=a[b[u]].end();++i)
            if(c[*i]==0)
                b[++l]=*i,c[*i]=1;
        ++u;
    }
    k=l;
}
}
}
out<<s;
}