- 软件开发
- planet distance 找环，并找和环上的距离
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
using namespace std
;
typedef long long ll
;
template<class T> using vv
=vector
<vector
<T
>>;
void bfs(const vv
<int>& edges
, const int x
, vector
<int>& mark
, vector
<int>& dis
, int N
) {
queue
<int> que
;
vector
<int> d(N
+ 1, 0x3f3f3f3f);
d
[x
] = 0;
que
.push(x
);
while (!que
.empty()) {
int top
= que
.front();
que
.pop();
for (const int& y
: edges
[top
]) {
if (mark
[y
] == 0) {
d
[y
] = min(d
[y
], d
[top
] + 1);
que
.push(y
);
mark
[y
] = 1;
}
}
}
for (int i
= 1; i
<= N
; ++i
) {
dis
[i
] = min(dis
[i
], d
[i
]);
}
}
int main() {
int T
;
int N
;
cin
>> T
;
int Case
= 1;
while (T
--) {
cin
>> N
;
vv
<int> edges(N
+ 1, vector
<int>());
map
<int,int> mp
;
queue
<int> que
;
vector
<int> vis(N
+ 1, 0);
for (int i
= 1; i
<= N
; ++i
) {
int a
,b
;
cin
>> a
>> b
;
edges
[a
].push_back(b
);
edges
[b
].push_back(a
);
mp
[a
] += 1;
mp
[b
] += 1;
}
for (int i2
= 1; i2
<= N
; ++i2
) {
if (mp
[i2
] == 1) {
que
.push(i2
);
}
}
while (!que
.empty()) {
int top
= que
.front();
que
.pop();
vis
[top
] = 1;
for (const int& x
: edges
[top
]) {
if (!vis
[x
]) {
mp
[x
] -= 1;
if (mp
[x
] == 1) {
que
.push(x
);
}
}
}
}
vector
<int> incircle
;
vector
<int> mark(N
+ 1, 0);
vector
<int> dis(N
+ 1, 0x3f3f3f3f);
for (int j
= 1; j
<= N
; ++j
) {
if (vis
[j
] == 0) {
incircle
.push_back(j
);
mark
[j
] = 1;
dis
[j
] = 0;
}
}
for (const int& x
: incircle
) {
bfs(edges
, x
, mark
, dis
, N
);
}
printf("Case #%d:", Case
);
for (int k
= 1; k
<= N
; ++k
) {
printf(" %d", dis
[k
]);
}
puts("");
Case
++;
}
return 0;
}
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <unordered_set>
using namespace std
;
typedef long long ll
;
template<class T> using vv
=vector
<vector
<T
>>;
void find_root(const vv
<int>& edges
, int root
, int father
, vector
<int>& vis
, unordered_set
<int>& circles
) {
vis
[root
] = 1;
int target
= -1;
for (const int& x
: edges
[root
]) {
if (x
== father
) continue;
if (vis
[x
] == 1) {
circles
.insert(x
);
}
else {
find_root(edges
, x
, root
, vis
, circles
);
}
}
}
void bfs(const vv
<int>& edges
, const int x
, vector
<int>& mark
, vector
<int>& dis
, int N
) {
queue
<int> que
;
vector
<int> d(N
+ 1, 0x3f3f3f3f);
d
[x
] = 0;
que
.push(x
);
while (!que
.empty()) {
int top
= que
.front();
que
.pop();
for (const int& y
: edges
[top
]) {
if (mark
[y
] == 0) {
d
[y
] = min(d
[y
], d
[top
] + 1);
que
.push(y
);
mark
[y
] = 1;
}
}
}
for (int i
= 1; i
<= N
; ++i
) {
dis
[i
] = min(dis
[i
], d
[i
]);
}
}
int main() {
int T
;
int N
;
cin
>> T
;
int Case
= 1;
while (T
--) {
cin
>> N
;
vv
<int> edges(N
+ 1, vector
<int>());
map
<int,int> mp
;
queue
<int> que
;
vector
<int> vis(N
+ 1, 0);
for (int i
= 1; i
<= N
; ++i
) {
int a
,b
;
cin
>> a
>> b
;
edges
[a
].push_back(b
);
edges
[b
].push_back(a
);
}
unordered_set
<int> circles
;
for (int j
= 1; j
<= N
; ++j
) {
int father
= -1;
vector
<int> vis(N
+ 1, 0);
find_root(edges
, j
, father
, vis
, circles
);
}
vector
<int> incircle
;
vector
<int> mark(N
+ 1, 0);
vector
<int> dis(N
+ 1, 0x3f3f3f3f);
for (const int& x
: circles
) {
incircle
.push_back(x
);
mark
[x
] = 1;
dis
[x
] = 0;
}
for (const int& x
: incircle
) {
bfs(edges
, x
, mark
, dis
, N
);
}
printf("Case #%d:", Case
);
for (int k
= 1; k
<= N
; ++k
) {
printf(" %d", dis
[k
]);
}
puts("");
Case
++;
}
return 0;
}
