Cod sursa(job #1754665)

Utilizator bogdanluncasubogdan bogdanluncasu Data 8 septembrie 2016 15:30:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<iostream>
#include<list>
#include<queue>
#include<algorithm>
using namespace std;
int n,m;
list<int> a[100001];
int viz[100001],c;
queue<int> q;
void dfs(int i){
	q.push(i);
	while(q.size()!=0){
		int p=q.front();
		q.pop();
		if(!viz[p]){
			viz[p]=1;
			for(list<int>::iterator it=a[p].begin();it!=a[p].end();){
				q.push(*it);
				a[*it].remove(p);
				a[p].erase(it++);				
			}
		}
	}		
	c++;
};
int main(){
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	int n1,n2;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
    	scanf("%d %d",&n1,&n2);
    	a[n1].push_back(n2);
    	a[n2].push_back(n1);
    }
	for(int i=1;i<=n;i++){
		if(!viz[i])dfs(i);
    }
	printf("%d",c);
}