9566 Term project

Term Project 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초	256 MB	13740	3439	2111	24.211%

문제

Students who enrolled in the ‘Problem Solving’ course in this fall semester have to carry out a term project. There is no limit to the number of project team members. Even one team is allowed such that all students are members of the same team. In order to form project teams, every student should select a friend with whom he or she wants to work. A student who wants to work alone can select himself or herself. A student list (s₁, s₂, ..., s_r) can be a team if either r=1 and s₁ selects s₁ or s₁ selects s₂, s₂ selects s₃, … , s_r-1 selects s_r, and s_r selects s₁.

For example, let’s assume that there are 7 students in the class. The students are numbered from 1 to 7. The following is the result of the selection.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

From the above result, we can see that two teams (3) and (4, 7, 6) are formed. Students 1, 2, and 5 don’t belong to any team.

Given the result of the selection, write a program to compute the number of students who don’t belong to a project team. 

입력

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer n (2 ≤ n ≤ 100 000), where n is the number of students in the class. All students are numbered from 1 to n. The next line of each test case contains n integers s₁, s₂, ..., s_n, where s_i is the student who was a student ݅ selected by. 

출력

Your program is to write to standard output. Print exactly one line for each test case. The line should contain the number of students who don’t belong to a project team. 

이틀을 투자해서 푼 문제다.

vector하나 더만들어서 저장하면되는데, 그러기 싫어서 계속 다른방법 찾다가 시간을 허비했다.

그냥 내 생각대로 tourist표정지으면서 짰더니 속도는 120등으로 낮지만, 통과는 했따!

#include <bits/stdc++.h>

using namespace std;

int students[100001];

bool grouped[100001];

bool visited[100001];

vector<int> chain;

vector<int> alone;

void chaining(int start);

bool isInChain(int student);

int main(){

freopen("input.txt","r",stdin);

ios::sync_with_stdio(false);

cin.tie(0);

int T;

cin>>T;

int n;

int temp;

for(int t=0; t<T; ++t){

chain = vector<int>();

alone = vector<int>();

memset(grouped, false, sizeof(grouped));

memset(visited, false, sizeof(visited));

cin>>n;

for(int _n=0; _n<n; ++_n){

cin>>temp;

students[_n] = temp-1;

}

for(int i=0; i<n; ++i){

if( !grouped[i] && !visited[i]){

chaining(i);

}

}

cout<<alone.size()<<"\n";

}

return 0;

}

void chaining(int start){

int pre;

chain.push_back(start);

visited[start] = true;

pre = start;

start = students[start];

while( !visited[ start ] ){

chain.push_back( start );

visited[start]=true;

pre = start;

start = students[start];

}

if( isInChain(start) ){

while(start != chain.back()){

grouped[chain.back()] = true;

chain.pop_back();

}

grouped[chain.back()] = true;

chain.pop_back();

while( !chain.empty() ){

alone.push_back(chain.back());

chain.pop_back();

}

} else {

while( !chain.empty() ){

alone.push_back(chain.back());

chain.pop_back();

}

}

}

bool isInChain(int student){

vector<int>::iterator iter;

for(iter = chain.begin(); iter!=chain.end(); ++iter){

if( *iter == student ){

return true;

}

}

return false;

}