題目描述:假如已知有n個人和m對好友關系(存于數字r)。如果兩個人是直接或間接的好友(好友的好友的好友...),則認為他們屬于同一個朋友圈,請寫程式求出這n個人裡一共有多少個朋友圈。
假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5個人,1和2是好友,2和3是好友,4和5是好友,則1、2、3屬于一個朋友圈,4、5屬于另一個朋友圈,結果為2個朋友圈。
輸入:
輸入包含多個測試用例,每個測試用例的第一行包含兩個正整數 n、m,1=<n,m<=100000。接下來有m行,每行分别輸入兩個人的編号f,t(1=<f,t<=n),表示f和t是好友。 當n為0時,輸入結束,該用例不被處理。
輸出:
對應每個測試用例,輸出在這n個人裡一共有多少個朋友圈。
樣例輸入:
5 3
1 2
2 3
4 5
3 3
1 2
1 3
2 3
樣例輸出:
2
1
備注:典型的圖的周遊問題(我用的dfs),求出連通分量個數。注意圖的資料結構用鄰接連結清單表示,用二維數組會超空間限制。
#include<iostream>
#include<vector>
using namespace std;
#define MAXNUM 100000
typedef struct person
{
vector<int> friends;
bool visited;
}Person;
Person *Graph;
int n,m;
void dfs(int start)
{
//Person p = Graph[start];
Graph[start].visited = true;
for(vector<int>::iterator iter = Graph[start].friends.begin();iter != Graph[start].friends.end(); iter++)
{
int f = *iter;
//Person pf = Graph[f];
if(!Graph[f].visited)
dfs(f);
}
}
int main()
{
int f,t;
int count;
cin>>n;
while(n>0)
{
cin>>m;
Graph = new Person[n+1];
for(int i=0;i<=n;i++)
{
Graph[i].visited = false;
}
for(int i=0;i<m;i++)
{
cin>>f>>t;
Graph[f].friends.push_back(t);
Graph[t].friends.push_back(f);
}
count = 0;
for(int i=1;i<=n;i++)
{
//Person p = Graph[i];
if(!Graph[i].visited)
{
dfs(i);
count++;
}
}
cout<<count<<endl;
delete[] Graph;
cin>>n;
}
return 0;
}