글 읽기 - dfs 관련 간절한 도움 필요합니다..... (4년전 질문도 답이 없습니다..)

n99joon 2년 전 2

제 코드는

각 노드에서 dfs 를 돌며

1. 모든 인접한 노드들을 색칠하고 (색칠이 안되어있으면)

2. 색칠이 되어 있으면 같은지 비교하고 (같으면 바로 끝)

3. dfs 끝났는데 모든 노드가 방문되어지지 않았으면, 방문되지 않은 노드부터 다시 dfs

를 합니다.

그런데 dfs 가 다 돌고 나서 다시 한번 더 인접한 노드가 같은 색인지 확인하지 않으면 (73~83 번쨰 줄)

실패가 나오고, 확인하면 통과합니다.

왜 굳이 마지막에 한번 더 확인해주어야하는지 도저히 모르겠습니다..

고수님들 도움 간절히 부탁드립니다..

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define endl '\n'
#define ll unsigned long long
using namespace std;

int main() {
	fastio;
	int tc, v, e, s, d;
	cin >> tc;
	while(tc--){
		cin >> v >> e;
		vector<int> edge[v+1];
		int visited[v+1]={0,};
		int ctr=0; // counts # of visited nodes
		int color[v+1]={0,};
		color[1]=1;
		int flag = 0; //0 if bipar 1 if not
        
		for(int i=0;i<e;i++){
			cin >> s >> d;
            if(s==d){
				cout <<"NO"<<endl;
				flag=1;
			}
			edge[s].push_back(d);
			edge[d].push_back(s);
		}
		if(flag)continue;
		
		stack<pair<int,int>> dfs; //src, dst
		dfs.push({1,1});
		while(!dfs.empty()){
			int src = dfs.top().first;
			int dst = dfs.top().second;
			dfs.pop();
			
			if(visited[dst])continue;
			visited[dst]=1;
			ctr++;
			
			//주변 모든 인접 노드 확인
			for(int i=0;i<edge[dst].size();i++){
				//color all edges and check colors
				int ds = edge[dst][i];
				 //색칠 안되어 있으면 색칠
				if(color[ds]==0){//not colored
					color[ds]=-color[dst];
				}
				//되어있으면 다른지 확인
				else{
					if(color[ds]==color[dst]){//same
						flag=1;
						break;
					}
				}
				
				if(!visited[edge[dst][i]]) 
					dfs.push({dst,edge[dst][i]});
			}
			if(flag) break;
			if(dfs.empty() && ctr<v){
				for(int i=1;i<=v;i++){
					if(visited[i]==0){
						dfs.push({i,i});
						color[i]=1;
						break;
					}
				}
			}
		}
        
  /*
		if(!flag)
		for(int i=1;i<=v;i++){
			for(int j=0;j<edge[i].size();j++){
				if(color[edge[i][j]]==color[i]){
					flag=1;
					break;
				}
			}
		}
        */
		if(flag)cout << "NO" << endl;
		else cout << "YES" << endl;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dfs 관련 간절한 도움 필요합니다..... (4년전 질문도 답이 없습니다..)

n99joon 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말