[백준] 15562 네트워크

 

문제 주소 : www.acmicpc.net/problem/15562

15562번: 네트워크

fast io 미적용

문제 확인

 

특별한 알고리즘이 필요없는 문제입니다.

문제에서 주어진 특성을 잘 이해하면 풀 수 있는 문제입니다.

 

풀이

 

A -> B, B -> C 라는 2개의 네트워크가 있을 때 이를 A -> C로 줄일 수 있습니다. 다시 말해 어떤 점에서 들어오는 선과 나가는 선이 있다면 이 둘을 합쳐 하나의 선으로 만들 수 있다는 것입니다.

이러한 성질을 이용해 들어오는 선이 1개 이상이며 나가는 선이 들어오는 선 이상일 경우를 합하면 답이 됩니다.

result += out - in > 0 ? out - in : 0

 

코드

#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, ary[1000001]={0}, res = 0;
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        ary[a]++; //나가는 선
        ary[b]--; //들어오는 
    }
    for (int i = 0; i < n; i++)
        res += ary[i] > 0 ? ary[i] : 0;
    cout << res;
}