DFS , dis-joint set (Union & Find 알고리즘)

DFS로 푼 것

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;
bool isfriend;
int n, m, ln, lm;
vector<int> map[1001];
int ch[1001];

void DFS(int s, int e){
	if(isfriend) return;
	if(s==e){
		isfriend = true;
		return;
	}
	else{
		for(int i=0; i<map[s].size(); i++){
			if(ch[map[s][i]]==0){
				ch[map[s][i]]=1;
				DFS(map[s][i], e);
				ch[map[s][i]]=0;
			}
		}	
	}
}


int main() {
	//freopen("input.txt.txt","rt",stdin);
	int i,a,b;
	scanf("%d %d", &n, &m);
	for(i=0;i<m;i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
		map[b].push_back(a);	
		
	}
	scanf("%d %d",&ln,&lm);
	ch[ln] = 1;
	DFS(ln, lm);
	if(isfriend) printf("YES");
	else printf("NO");
	
	return 0;	
}

 

dis-joint set(Union & Find 알고리즘)

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;

int unf[1001];

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v] = Find(unf[v]);
	
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a]=b;
}



int main() {
	//freopen("input.txt.txt","rt",stdin);
	ios_base::sync_with_stdio(0);
	
	int n, m, a, b;
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		unf[i]=i;
	}
	
	for(int i=1; i<=m; i++){
		cin>>a>>b;
		Union(a,b);
	}
	cin>>a>>b;
	a=Find(a);
	b=Find(b);
	if(a==b) cout << "YES";
	else cout <<"NO";
	return 0;
	
	

	return 0;	
}