-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdfsSpanningTree_temp.cpp
85 lines (67 loc) · 1.58 KB
/
dfsSpanningTree_temp.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define endl "\n"
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<int,int,int> tp;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector <ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unordered_map<int, int> mpii;
int T,n;
vi v[100001];
bool visited[100001];
bool finished[100001];
bool iscycle[100001];
int parent[100001];
int cnt;
void cycle(int node, int next){
iscycle[node] = true;
cnt++;
if( node == next) return;
cycle(parent[node], next);
}
void dfs(int node){
visited[node] = true;
for(int i=0; i<v[node].size(); i++){
int next = v[node][i];
if(!visited[next]){
parent[next] = node;
dfs(next);
}
else if(!finished[next]){ //종료되지 않은 정점이라면 사이클
cycle(node, next);
}
}
finished[node] = true;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> T;
while(T--){
cin >> n;
cnt=0;
for(int i=0; i<=n; i++){
v[i].clear();
parent[i] = i;
visited[i] = false;
finished[i] = false;
iscycle[i] = false;
}
for(int i=1; i<=n; i++){
int a;
cin >> a;
v[i].push_back(a);
}
for(int i=1; i<=n; i++){
if(!visited[i])
dfs(i);
}
cout << n - cnt << endl;
}
}