Cod sursa(job #731111)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 7 aprilie 2012 15:11:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> list[100005];
bool viz[100005];
queue<int> q;
void parcurge()
{
	while(q.size())
	{
		int urmnod=q.front();
		q.pop();
		for(unsigned int i=0;i<list[urmnod].size();i++)
		{
				if(viz[list[urmnod][i]]==0)
				{
					q.push(list[urmnod][i]);
					viz[list[urmnod][i]]=true;
				}
		}
	}
        
}
 
int main()
{
        int n,m,nrc=0;
        freopen("dfs.in","r",stdin);
        freopen("dfs.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)
        {
                int x,y;
                scanf("%d %d",&x,&y);
                list[x].push_back(y);
                list[y].push_back(x);
        }
        for(int i=1;i<=n;i++)
        {
                if(viz[i]==0)
                {
                        viz[i]=1;
                        nrc++;
						q.push(i);
                        parcurge();
                }
        }
        printf("%d",nrc);
        
        return 0;
}