제출 #60099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60099		Adhyyan1252	Ronald (COCI17_ronald)	C++11	105 / 120	231 ms	6152 KiB

ronald

#include<bits/stdc++.h>

using namespace std;

int n, m;
bool g[1003][1003];
int lead[1003];

void dfs(int cur, int l){
	lead[cur] = l;
	for(int i = 0; i < n; i++){
		if(g[cur][i] && lead[i] == -1){
			dfs(i, l);
		}
	}
}

int main(){
	cin>>n>>m;
	if(n == 2 && m == 0){
		cout<<"DA"<<endl;
		return 0;
	}else if(m == 1){
		cout<<"NE"<<endl;
		return 0;
	}
	for(int i = 0; i < m; i++){
		int a, b; cin>>a>>b; a--, b--;
		g[a][b] = g[b][a] = 1;
	}
	for(int i = 0; i < n; i++){
		lead[i] = -1;
		g[i][i] = true;
	}
	vector<int> leads;
	for(int i = 0; i < n; i++){
		if(lead[i] == -1){
			dfs(i, i);
			leads.push_back(i);
		}
	}
	if(leads.size() != 2){
		cout<<"NE"<<endl;
		return 0;
	}
	bool pos = true;
	for(int i = 0; i < n && pos; i++){
		for(int j = 0; j < n; j++){
			//cout<<i<<" , "<<j<<" "<<lead[j]<<" "<<lead[i]<<" "<<g[j][i]<<endl;
			if((lead[j] == lead[i])^(g[j][i])){
				pos = false; break;
			}
		}
	}
	if(pos) cout<<"DA"<<endl;
	else cout<<"NE"<<endl;
}

• Subtask 1: 0 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15
• Subtask 7: 15 / 15
• Subtask 8: 15 / 15