[c++]백준 #9466 텀프로젝트

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

< 풀이 방법 >

1) DFS를 돌리면서 starting point부터 번호를 하나씩 매김(배열 dist 이용).

2) DFS가 시작될 때마다 graph number를 새로 부여(변수 ng) 이용

3) DFS를 돌다가 같은 그래프 내의 이미 방문한 점을 만나게 되면 그 점이 나오기 전까지의 노드는 cycle에 속하지 않으므로 cycle이 생기기 전까지의 노드의 개수를 배열 dist에 접근하여 더해줌

e.g. 예시에서 1->3->3 순으로 노드를 방문하게 되는 경우 노드 1은 팀을 이루지 못함

4) DFS를 돌다가 다른 그래프 내의 이미 방문한 점을 만나게 되면 그 전 노드까지 노드의 개수를 배열 dist에 접근하여 더해줌

e.g. 예시에서 이미 1->3->3을 돈 상태에서 2가 1을 만나게 되는 경우 노드 2도 팀을 이루지 못함.

    #include <iostream>
    #include <string>
    #include <vector>
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h> 
    #include <string.h>
    #include <cstdio>
    #include <math.h>
    #include <map>
    #include <algorithm>
    #include <queue>
    using namespace std;
 
    // variables
    int dist[100001]; // stores the distance of nodes in graph from starting point
    int cnt = 0; // variable for counting nodes which is not a member of any cycled graph
    int T = 0;
    int N = 0;
    int ng = 0;
 
    void DFS(int start, vector<int>*connect, int* search, int ng, int d)
    {
        search[start] = ng; // start node searched!
        dist[start] = d;
 
        // search every nodes connected with current node
        for (int i=0; i<connect[start].size();i++) 
        {
            int next = connect[start][i];
            if (!search[next]) // not visited yet
            {
                DFS(next, connect, search, ng, d+1);
            }
            else if (search[next] == ng)// already visited next node at same graph
            {
                cnt += dist[next] - 1; 
            }
            else // already visited but not same graph
            {
                cnt += dist[start];
            }
        }
    }   
 
    
 
    int main()
    {
        ios_base :: sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        cin >> T;
        for (int i=0; i< T; i++)
        {
            // initialize variables at every test cases 
            ng = 0;
            cnt = 0;
            cin >> N;
            vector<int> connect[N+1]; // stores the graph connections
            int search[N+1]; // stores which node has been visited or not 
            fill(search, search+N+1, 0); // initialize all search array elements as 0
 
            // input processing
            for (int i=1;i<=N;i++)
            {
                int elem;
                cin >> elem;
                connect[i].push_back(elem);
            }
 
            // sorting
            for(int i=1;i<=N;i++)
            {
                sort(connect[i].begin(),connect[i].end());
            }
            
            // DO DFS
            for (int i=1;i<=N;i++)
            {
                if (!search[i]) // if not searched yet
                {
                    ng++; // number of graph
                    DFS(i, connect, search, ng, 1);
                }
            }
            cout <<  cnt << '\n';
        }
        
 
        return 0;
    }