Codeforces Round #405 (Div. 2) B

Codeforces Round #405 (Div. 2)

B. Bear and Friendship Condition

http://codeforces.com/contest/791/problem/B

그래프가 주어진다.

노드 개수는 15만개이고 간선개수도 최대 15만개를 넘지 않는다. (두 정점간 간선은 두개 이상 존재할 수 없다.)

1,2,3이 친구라면 1-2, 2-3, 1-3 모두 연결되어있어야 친구다.

4명이 존재하면 4번 친구는 그냥 혼자 있거나 친구가 있어야 하는 그런 문제였다.

그러니까... 부분그래프가 완전그래프를 그리는지를 판별하는 거였는데,

정점개수가 n개가 친구를 먹으려면 각 정점마다 n-1개의 간선이 있는지 보면 된다.

문제는 ㅠ.. 난 그냥 모든 정점의 간선개수가 같다고 풀어버려서 4분 남기고 핵먹었음.

아래 테케는 핵당한 테케

Examples

input

4 4
1 2
2 3
3 4
4 1

output

NO

#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector<int> v[150001];
int chk[150001], cnt;
bool ans=true;
stack<int> s;
void dfs(int x) {
    chk[x]=true;
    s.push(x);
    cnt++;
    for(int y: v[x]) {
        if(chk[y]) continue;
        else dfs(y);
    }
}
int main() {
    int n, k;
    scanf("%d%d",&n,&k);
    int a,b;
    for(int i=0; i<k; i++) {
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=0; i<n; i++) {
        if(chk[i]) continue;
        else {
            cnt=0;
            dfs(i);
            while(!s.empty()) {
                int x=s.top(); s.pop();
                if(v[x].size()!=cnt-1) return 0&puts("NO");
            }
        }
    }
    puts("YES");
    return 0;
}