글 읽기 - 반례를 못찾겠습니다..

hojinland 6년 전 0

BFS방법을 통해 풀었습니다.

학생이 시작해 연결되어 있는 학생들을 따라가고 마지막 학생과 시작학생을 비교했을때 같은 경우 cycle이 존재해

sum에 포함시키지 않았습니다.

이외의 학생을 sum으로 출력했습니다.

#include <iostream>
#include <queue>
#include <string>
#include <vector> 
#include <cstdio>
using namespace std;
int student[100001] = {0,};

int main(){
	vector<pair<int,int>> v;
	int a , b , temp;// 실행 횟수
	cin>>a;
	int now;
	queue<int> q;
	int cnt;
	int sum ; // 잘못된갯수
	for(int j = 0 ; j < a ; j++){
		cin>>b;
		sum = 0 ;
		student[0] = 0;
		for(int i = 1 ; i <= b ; i ++){
			student[i] = 0;
			cin>>temp;
			v.push_back(make_pair(i,temp));			
		}
		for(int i = 1 ; i <= b ; i ++){
			if(student[i] != 0)continue;
			q.push(i);
			student[i] = i;
			cnt = 0 ;
			while(!q.empty()){
				cnt++;
				now = q.front();
				q.pop();
				if(student[v[now-1].second] == 0 && v[v[now-1].second].second != v[v[now-1].second].first){
					q.push(v[now-1].second);
					student[v[now-1].second] = i;
				}
			}
			if(i == v[now-1].second ) cnt = 0;
			else sum += cnt;
		}
		cout<<sum<<endl;
		v.erase(v.begin(),v.end());
	}
	
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 못찾겠습니다..

hojinland 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말