백준 23324 (어려운 모든 정점 쌍 최단거리)

https://www.acmicpc.net/problem/23324

23324번: 어려운 모든 정점 쌍 최단 거리

매우 흥미로운 문제였다. 
플로이드 와샬이라는 알고리즘을 지문에 제시해두고 그거 안되니깐 다른거로 풀어봐라 이런 것도 좋았고, 

가중치 있는 간선이 딱 하나인 것도 좋았다. 물론 여러개의 간선에 가중치가 존재하게 된다면 문제는 완전 다른 문제가 되겠지만 

 

관찰 문제이다. 

 

만약 가중치 있는 간선 사이 두 정점이 u, v인 경우 

 

u로 이루어진 컴포넌트와 v로 이루어진 컴포넌트 대략적으로 두가지 컴포넌트가 존재한다고 할 때, 모든 정점끼리의 잇는 정점쌍의 갯수는 N-x * x (x := 어떤 컴포넌트를 이루는 정점의 갯수) 이 된다. 

 

근데 여기서 예제 2를 보면 0이 나오는 케이스가 존재하게 된다.

 

예제 2처럼 u -> v 를 cost 0으로 갈 수 있다면 이 케이스는 0이되는 것이다. 

 

머 구현은 잘 dfs로 방문체크로만 해도 가능하다

 

이런 문제가 너무 좋다 참으로 educational한 문제인 것 같다. 

 

#include <bits/stdc++.h>

using namespace std;
#define TEST int tt; cin >> tt; while (tt--)
#define all(v) (v).begin(), (v).end()
#define loop(e, v) for (auto& (e) : (v))
#define mem(v, e) memset((v), (e), sizeof(v))
#define _unique(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
#define ld long double
const int MAX = 100'005;
const int INF = 1e9 + 1;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

vector<int> v[MAX];
bool visited[MAX];
int start, start2;
ll cnt;
bool flag;

void dfs(int now, int num) {
    visited[now] = true;
    cnt++;
    for(int i=0; i<v[now].size(); i++){
        int nxt = v[now][i];
        if(now!=start && nxt == start2)flag=true;
        if(visited[nxt])continue;
        dfs(nxt, num+1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N, M, K;
    cin >> N >> M >> K;
    for(int i=1; i<=M; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
        if(i==K){
            start = a;
            start2 = b;
            visited[b] = true;
        }
    }
    dfs(start, 0);
    if(flag)cout <<0;
    else cout << (N-cnt)*cnt;
}