[白俊]9466号休止項目

質問リンク:https://www.acmicpc.net/problem/9466

質問する

この秋学期、「問題解決」課程を申請した学生たちは臨時プロジェクトを完成しなければならない.プロジェクトチームメンバーの数に制限はありません.すべての学生が同じチームのメンバーであるように、1つのチームしかないかもしれません.プロジェクトチームを作るためには、学生一人一人が一緒にプロジェクトに参加したい学生を選ぶべきだ.△選択できるのは一人だけです.一人でやりたい学生は自分を選ぶことができます.
学生が(s 1,s 2,...,sr),r=1,s 1がs 1,s 1がs 2,s 2がs 3,...sr-1がsrを選択し、srがs 1を選択した場合にのみ、チームになります.
例えば、1つのクラスには7人の学生がいます.学生を1日から7日まで表現する場合、選択した結果は以下の通りです.

以上の結果から,(3)と(4,7,6)は1つのチームを構成することができる.1,2,5はどのチームにも属していません.
与えられた選択結果に基づいて、任意のプロジェクトチームに属さない学生数を計算するプログラムを作成します.

入力

第1行は、試験例の個数Tを与える.各試験例の最初の行に与えられた学生数は整数n(2≦n≦100000)であった.各テストケースの2行目には、選択した学生の番号が表示されます.△すべての学生は1からnまで番号付けされている.

しゅつりょく

各テストケースは、プロジェクトチームに属していない学生の数を示す行を出力します.

問題を理解する

方向性のあるグラフィックで、1つのノード(学生)が1つだけ外に出るノードを許可します.したがって,これは無ループノード(学生)数を求める問題である.

質問へのアクセス

どの学生がどの学生を選択したかに関する情報、ループがあるかどうか、またはノードにナビゲートしたかどうかの情報.
1.入力の受信
2.ノードを1つずつブラウズし、checkに0とマークが付いている場合は、その部分からdfsを開始します.dfsでは、次のノードが2または-1の場合は続行されません.
3.ナビゲーションが終了したら、自分のノードをチェックし、2でなければ-1を表示します.
4.すべてのノードを参照します.
5.dfsが完了したら、ノードに2以外のものを1つ数えます.
6.出力.
7.テストケースのように2～6回繰り返します.

実装上の問題(C++)

#include <iostream>

using namespace std;

int testcase;
int studentNum;
int check[100001];
int selectNum[100001];

int noTeamStudentCheck(){
    int cnt = 0 ;
    for(int i = 1 ; i <= studentNum ; i++){
        if(check[i] != 2) cnt++;
    }
    return cnt;
}
void search(int curNode){
    check[curNode]++;
    int nextNode = selectNum[curNode];
    if(check[nextNode] != 2 && check[nextNode] != -1){
        search(nextNode);
    }
    if(check[curNode] != 2) check[curNode] = -1;

}
void dfs(){
    for(int i = 1 ; i <= studentNum ; i++){
        if(check[i] == 0){
            search(i);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> testcase;
    for(int i = 0 ; i < testcase ; i++){
        cin >> studentNum;
        for(int j = 1 ; j <= studentNum ; j++){
            cin >> selectNum[j];
            check[j] = 0;
        }
        dfs();
        cout << noTeamStudentCheck() << "\n";
    }
    
    


}

評価

この問題の冒頭は0ではなく、1です.だからそれに対する思いを持って符号化しなければならない.私はこのように始まったのではなく、少し時間がかかりましたが、すぐに見つけて、よく解決しました.