[1325번] 효율적인 해킹

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 단방향 그래프

2. dfs

이 문제는 a->b가 신뢰한다면 결국 b->a로 해킹 할 수 있다는 것이다.

따라서 예제 입력인

3 1

3 2

4 3

5 3

를 본다면 아래와 같은 단방향 그래프가 형성되는 것이다.

결국 자신으로부터 종속된 노드가 몇개가 있는지 찾는 것이고(이 과정을 해킹이라고 말하고 있다.)

가장 많이 종속하고 있는(여러개가 될 수 도 있다.(여기선 1,2가 답)) 노드를 출력하는 것이다.

따라서 dfs를 통해 자신의 노드의 개수를 구하면 되는 문제.

아래 코드는 실질적으로 자신을 포함한 노드 개수가 나타나는데

cnt[i] = dfs(i) - 1;로 고쳐주면 온전한 자식 노드의 개수만 구할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <memory.h>
 
using namespace std;
 
vector<int> vc[10001];
bool visit[10001];
int tmp[10001];
int cnt[10001];
vector<int> ans;
 
// 자신을 포함한 자식 노드 전체 개수 구하는 알고리즘
int dfs(int start)
{
    if (visit[start] == true)
        return 0;
 
    visit[start] = true;
 
    for (int i = 0; i < vc[start].size(); i++)
    {
        int there = vc[start][i];
 
        tmp[start] += dfs(there);
    }
 
    return tmp[start] + 1;
}
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
        vc[to].push_back(from);
    }
 
    for (int i = 1; i <= n; i++)
    {
        memset(visit, false, sizeof(visit));
        memset(tmp, 0, sizeof(tmp));
        cnt[i] = dfs(i);
    }
 
    // 정렬 알고리즘
    int MAX = cnt[1];
    ans.push_back(1);
 
    for (int i = 2; i <= n; i++)
    {
        if (cnt[i] > MAX)
        {
            ans.clear();
            MAX = cnt[i];
 
            ans.push_back(i);
        }
        else if (cnt[i] == MAX)
            ans.push_back(i);
    }
 
    sort(ans.begin(), ans.end());
 
    int len = ans.size();
    for (int i = 0; i < len; i++)
        printf("%d ", ans[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>