BOJ-9466基準項目

2427 ワード
DFS boj テキストリンク
9466号基準項目
これは、一時的なプロジェクトを行うためにチームを選択した場合、どのチームにも属しない学生の数の問題です.
例えば、1番の学生がチームを組む場合は、1番と2番がチームで、2番が3番と3番がチームであれば、1、2、3番がチームです.逆に、3番と2番が同じチームであれば、2、3番はチームになり、1番はチームに属していない場合です.
問題を解決するためにdfsアルゴリズムを用いた.
問題の解決過程は以下の通りである.
  • dfsにより、深さは1回ごとに+1になる.
  • ノードがすでにアクセスしている場合、ノードは他のチームメンバーを指定し、誰かに指定されているため、ノードをグループ長に任命し、これまでの深さをfinalに保存します.
  • が通った道を戻って、一人一人がdept-1をします.
  • 戻り時にノードがグループ長である場合、finalにdepth-1が保存されます.
    • たとえば、1(2)->2(4)->4(3)->3(2)の場合、最後のノードが希望するチームメンバーは2番ですが、2番はすでに指定されていて、指定された状態にあるので組長になります.
    (final=4,depth=4)
    組長は2番なので、帰る途中で今ノードが2番ならチームにならなかった方が1番になります.
    (final=1状態)
    逆に、3番が5番(3(5))になり、5番がすでにあるチームに所属している場合、1、2、3、4番はいずれもチームになれない選手になる.
    (final=4)
    コード#コード#
    #include <iostream>
#include <vector>

using namespace std;

int visited[100001];
vector<int>v[100001];
int cnt;
int n;
int team;
int depth;
int final;

void dfs(int s)
{
    if(visited[s] == 1)
    {
        team = s;
        final = depth;
        return;
    }

    final = 1;

    visited[s] = 1;
    depth++;

    dfs(v[s][0]);

    if(team == s)
    {
        final = depth-1;
    }
    depth--;

    return;
}

void sol()
{
    cin >> n;

    for(int i=1;i<=n;i++)
    {
        visited[i] = 0;
    }

    cnt = 0;

    for(int i=1;i<=n;i++)
    {
        int p;
        cin >> p;
        v[i].push_back(p);
    }

    for(int i=1;i<=n;i++)
    {
        team = -1;
        final = 0;
        dfs(i);
        cnt += final;
    }

    cout << cnt << "\n";

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    for(int i=0;i<t;i++)
    {
        sol();

        for(int i=1;i<=n;i++)
        {
            v[i].clear();
        }
    }
    return 0;
}
    ソース:https://www.acmicpc.net/problem/9466
    モデルとジャンゴスターター
    #10 DBMS DCL,KEY修正中