Cod sursa(job #2003072)

Utilizator 00MikeComputer00Mihnea Andreescu 00MikeComputer00 Data 21 iulie 2017 17:59:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
const int nm=100005;
vector<int>G[nm];
queue<int>q;
int viz[nm],d[nm],t[nm];
void BFS(int nod,int nr)
{
	q.push(nod);
	viz[nod]=nr;
	while(!q.empty())
	{
		int y=q.front(),x=G[y].size(),i;
		q.pop();
		for(i=0;i<x;i++)
			if(!viz[G[y][i]])
			{
				viz[G[y][i]]=nr;
				d[G[y][i]]=d[y]+1;
				t[G[y][i]]=y;
				q.push(G[y][i]);
			}
	}
}
int main()
{
	int n,m,i,u,v,nr=0;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(i=1;i<=n;i++)
		if(!viz[i])
			BFS(i,++nr);
	int ma=0;
	for(i=1;i<=n;i++)
		ma=max(ma,viz[i]);
	cout<<ma;
	cin.close();
	cout.close();
	return 0;
}