APCS程式檢測 -實作題1060304 第2題 小群體

APCS程式檢測 -實作題1060304 第2題 小群體

建立一個是否被追蹤過的陣列
從一個沒被追蹤過的人開始
追蹤他的好友、好友的好友
直到已被追蹤過
就是一個小團體

再繼續找一個沒被追蹤過的人開始

完整程式碼

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main()
{
	//輸入團體人數
	string strInput;
	getline(cin, strInput);
	int N = stoi(strInput);

	//建立好友編號陣列
	int* nFriend = new int[N];
	string strInput2;
	getline(cin, strInput2);
	stringstream delim2(strInput2);
	string pch2;
	for (int i = 0; i < N; i++)
	{
		getline(delim2, pch2, ' ');
		nFriend[i] = stoi(pch2);
	}

	//建立追蹤陣列
	bool* bTrace = new bool[N];
	for (int i = 0; i < N; i++)
		bTrace[i] = false;

	//開始追蹤
	int k = 0;
	int j = false;
	int nGroup = 0;
	for (int i = 0; i < N; i++)
	{
		if (bTrace[i] == false)	//找一個沒被追蹤過的人
		{
			nGroup++;	//小團體數量+1

			k = i;
			j = bTrace[k];
			bTrace[k] = true;

			while (j == false)
			{
				k = nFriend[k];		//陣列資料中的下一個人
				j = bTrace[k];		//是否被追蹤過
				bTrace[k] = true;	//標示已被追蹤過
			}
		}
	}

	cout << nGroup << endl;

	delete[] nFriend;
	delete[] bTrace;

	system("pause");
	return 0;
}