我的朋友很少

簡單的 DFS 新手練習,其實還有比較簡潔的作法,個人是另外開了一個 Time 陣列來儲存好友組別,藉以區分有沒有朋友的朋友。

a445: 新手訓練系列- 我的朋友很少:

內容:

我的朋友很少~ 但是朋友的朋友就是我的朋友!

輸入說明:

第一行有三個正整數 N , M , Q ( N <= 10000 , M <= 10000 , Q <= 100000 )

代表有 N 個人 , M 筆朋友關係 , Q 筆詢問

接下來有 M 行, 每行有兩個正整數 A , B ( A,B <= N )

代表 A 和 B 有 朋友 關係

再來有 Q 行, 每行兩個正整數 P , Q ( A,B <= N )

輸出說明:

請輸出 P 和 Q 是不是朋友

如果是請輸出 ":)"

否則請輸出 ":("
範例輸入 : help

5 3 2
1 2
2 5
3 4
1 5
1 3 

範例輸出:(一行一個輸出)

:)
:(

DFS 解

#include<stdio.h>
#include<vector>
using namespace std;
vector <int>ship[10001];
int q,m,n;
int a,b;
int color[10001]={0};
int Time[10001]={0};
int tmp_time = 0;
int tmp_a,tmp_b;
void dfs(int x,int y);
int main(){
	scanf("%d%d%d",&n,&m,&q);
	// 朋友關係 
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		ship[a].push_back(b);
		ship[b].push_back(a);	
	}
	//遍歷 && 設定 time
	 
	for(int i=1;i<=n;i++){
		if(color[i]==0)dfs(i,tmp_time);
		tmp_time ++;
	}
	// 判斷 time 是否相等 
	for(int i=0;i<q;i++){
		scanf("%d%d",&tmp_a,&tmp_b);
		if( Time[tmp_a] == Time[tmp_b] )printf(":)\n");
		else printf(":(\n");
	}
}
// DFS
void dfs(int x,int y){
	color[x] = 1;
	Time[x] = y;
	for(int i=0;i<ship[x].size() ;i++){
		int tmp = ship[x][i];
		if(color[tmp]==0)dfs(tmp,y);
	}
}

另解:disjoint set

#include <stdio.h>
#include <algorithm>
#define MAXN 1000005
int parent[MAXN];//每個點紀錄其父母節點
int size[MAXN];//每個點紀錄以它為根的子樹的大小
int n,m,q;
int tmp_a,tmp_b;
int a,b;
void MAKE_SET(int x){
    parent[x]=x;
    size[x]=1;
}
void init(int n){
    for(int i=0;i<n;++i){
        MAKE_SET(i);
    }
}
int FIND_SET(int x){
    if(parent[x]==x)return x;
    parent[x]=FIND_SET(parent[x]);
    return parent[x];
}
bool UNION(int x,int y){
    x=FIND_SET(x);
    y=FIND_SET(y);
    if(x==y)return false;
    if(size[x]<size[y]){
        std::swap(x,y);
    }
    parent[y]=x;
    size[x]+=size[y];
    return true;
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	init(n);
	for(int i=0;i<m;i++){
		scanf("%d%d",&tmp_a,&tmp_b);
		UNION(tmp_a,tmp_b);
	}
	for(int i=0;i<q;i++){
		scanf("%d%d",&a,&b);
		if( FIND_SET(a) == FIND_SET(b) )printf(":)\n");
		else printf(":(\n");
	}
}

pixiv