백준 1325 // 자식수찾기는 int dfs(ret=1, ret+=dfs)

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

1325번: 효율적인 해킹

※ 문제 : int i=1~ 일때 ret.push 후 max갱신(현재, ret[i])참조하면 다른값이참조됨

해결 : int f에 저장, push(f), max갱신(현재vsf)

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int m, n, a, b, del, v[10004], dp[10004], mx;
//vector<vector<int>> adj(104,vector<int>(104,0));    //(크기,초기화대상)
vector<int> adj[10004];    //2차원벡터 선언방법
vector<pair<int, int>> ret;
int dy[] = {1,0,-1,0};
int dx[] = {0,1,0,-1};

bool cmp(pair<int,int> a, pair<int,int> b)
{
    return a.first < b.first;
}

int dfs(int here)
{
    v[here] = 1;    //adj쓰는경우 방문은 필요없다? ㄴㄴ
    
    int ret = 1;    
    //문제 : 0으로 하면 누적이안됨
    //해결 : 1로하고, 최대값만 구하면되므로 실제 자식수랑일치할필요X
    for (auto there:adj[here])
    {
        if (v[there]) continue;
        ret += dfs(there);
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n>>m ;
    for (int i = 0; i < m; ++i)
    {
        cin >> a>>b;
        adj[b].push_back(a);
    }
    //디버깅
    /*for (int i = 1; i <= n; ++i)
    {
        for (auto p : adj[i])
            cout << i<<"에연결된노드 " << p<<" "<<endl;
    }*/

      for (int i = 1; i <= n; ++i)
    {
        fill(&v[0], &v[10004], 0);
        int f = dfs(i);
        ret.push_back({ f,i });
        mx = max(mx, f);
    } 
    //sort(ret.begin(), ret.end(),cmp);

    //디버깅
    /*for (pair<int, int> p : ret)
    {
        cout << "연결노드수: " << p.first 
            <<"노드번호: " << p.second<<endl;
    }*/

    //int max = ret[ret.size()-1].first;
    for (pair<int, int> p : ret)
    {
        if (p.first == mx) cout << p.second << " ";
    }

    /*for (int i = 1; i <= n; i++) {
        memset(v, 0, sizeof(v));
        dp[i] = dfs(i);
        mx = max(dp[i], mx);
    }
    for (int i = 1; i <= n; i++) if (mx == dp[i]) cout << i << " ";*/

    return 0;
}