16041번 - Double Clique
[문제]
무방향 그래프 $G$가 주어진다. 이 그래프에는 $n$개의 노드와 $m$개의 간선이 있다. 정점들의 집합을 $V$, 간선들의 집합을 $E$하고 하자.
그래프 $G$의 여그래프를 $G'$라고 정의한다. 여그래프 $G'$는 $G$와 동일한 노드를 가지며, 다음과 같은 규칙으로 간선이 정의된다.
- 만약 $G$에 노드 $a$와 $b$ 사이에 간선이 없다면, $G'$에는 $a$와 $b$ 사이에 간선이 존재한다.
- 만약 $G$에 노드 $a$와 $b$ 사이에 간선이 있다면, $G'$에는 $a$와 $b$ 사이에 간선이 존재하지 않는다.
클리크(Clique)는 모든 노드 쌍이 연결된 정점 부분 집합을 의미한다.
노드의 부분 집합 $S$가 다음을 만족하면 더블 클리크(Double clique)라고 정의한다.
1. $S$는 $G$에서 클리크이다.
2. $V-S$($S$를 제외한 나머지 노드 집합)은 $G'$에서 클리크이다.
참고 : 빈 노드 집합도 클리크로 간주한다.
[입력]
입력은 단일 테스트 케이스로 이루어진다.
첫 번째 줄에 두 정수$n$, $m$이 공백으로 구분되어 주어진다. ($1 \le n, m \le 2 \times 10^5$)
다음 $m$개의 줄 각각에는 두 정수 $a$, $b$가 공백으로 구분되어 주어진다.($1 \le a, b \le n$)
모든 간선이 유일함이 보장된다.
[출력]
그래프의 더블 클리크의 개수를 $10^9+7$로 나눈 나머지를 출력한다.
댓글을 작성하려면 로그인해야 합니다.
realpsdoingdamyoo 1년 전 2
[문제]
무방향 그래프 $G$가 주어진다. 이 그래프에는 $n$개의 노드와 $m$개의 간선이 있다. 정점들의 집합을 $V$, 간선들의 집합을 $E$하고 하자.
그래프 $G$의 여그래프를 $G'$라고 정의한다. 여그래프 $G'$는 $G$와 동일한 노드를 가지며, 다음과 같은 규칙으로 간선이 정의된다.
- 만약 $G$에 노드 $a$와 $b$ 사이에 간선이 없다면, $G'$에는 $a$와 $b$ 사이에 간선이 존재한다.
- 만약 $G$에 노드 $a$와 $b$ 사이에 간선이 있다면, $G'$에는 $a$와 $b$ 사이에 간선이 존재하지 않는다.
클리크(Clique)는 모든 노드 쌍이 연결된 정점 부분 집합을 의미한다.
노드의 부분 집합 $S$가 다음을 만족하면 더블 클리크(Double clique)라고 정의한다.
1. $S$는 $G$에서 클리크이다.
2. $V-S$($S$를 제외한 나머지 노드 집합)은 $G'$에서 클리크이다.
참고 : 빈 노드 집합도 클리크로 간주한다.
[입력]
입력은 단일 테스트 케이스로 이루어진다.
첫 번째 줄에 두 정수$n$, $m$이 공백으로 구분되어 주어진다. ($1 \le n, m \le 2 \times 10^5$)
다음 $m$개의 줄 각각에는 두 정수 $a$, $b$가 공백으로 구분되어 주어진다.($1 \le a, b \le n$)
모든 간선이 유일함이 보장된다.
[출력]
그래프의 더블 클리크의 개수를 $10^9+7$로 나눈 나머지를 출력한다.