基环树

基环树

知识点来自：基环树

1.基环树

众所周知树的性质，即对于一个有 \(n\) 个节点的树，必定保证有 \(n−1\) 条边（无向边）。反过来，对于一个由 \(n−1\) 条无向边组成的连通图，必定是一棵树。据此，明显的，对于一个有 \(n\) 个结点 \(n\) 条边的无向连通图，必定是在一棵树上的任意两个节点之间连一条边构成的。我们把 \(n\) 个节点 \(n\) 条边的无向连通图，就称为基环树。

2.基环树森林

基环树森林可以视作是许多基环树的集合。基环树森林同样是 n 个节点 n 条边，但不一定保证连通。

3.内向树/外向树

可以视作有向图中的基环树吧，同样是 n 个节点 n 条边，不过这里的边是有向边，内向树中每个点有且仅有一条出边，外向树中每个点有且仅有一条入边。

CF131D

题目大意

给出一个 \(n\) 个点，\(n\) 条边的无向无权图，图上每条边的长度为 \(1\)，保证图中有且仅由一个环。

你的任务是求出每一个点到环（环上任意一点）的最短路径长度。

\((3 \leq n \leq 3 \times 10^3)\)

code

/*Work by:Ariel_*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3010;
int read() {
  int x = 0, f = 1; char c = getchar();
  while(c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}
  while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  return x * f;
}
int st[MAXN], top, vis[MAXN], loop[MAXN], cnt, fag;
struct edge{int v, nxt;}e[MAXN << 1];
int E, head[MAXN];
void add_edge(int u, int v) {
  e[++E] = (edge) {v, head[u]};
  head[u] = E;
}
void Get(int u, int f) {
   if(fag) return ;
   st[++top] = u, vis[u] = 1;
   for (int i = head[u]; i; i = e[i].nxt) {
   	   int v = e[i].v;
	   if (v == f) continue;
	   if(vis[v]) {
	   	  loop[v] = ++cnt;
	   	  for (;st[top] != v; --top) loop[st[top]] = cnt;
	   	  top--, fag = 1; return ;
	   } 
	   Get(v, u);
	   st[--top], vis[v] = 0;
   }
}
int dis[MAXN], N;
void dfs(int x) {
  for (int i = head[x]; i; i = e[i].nxt) {
  	  int v = e[i].v;
  	  if(dis[v] || loop[v]) continue;
  	  dis[v] = dis[x] + 1;
  	  dfs(v);
  }
}
int main(){
  N = read();
  for (int  i = 1; i <= N; i++) {
  	int u = read(), v = read();
  	add_edge(u, v), add_edge(v, u);
  }
  fag= 0;
  Get(1, 0);
  for (int i = 1; i <= N; i++) {
  	 if(loop[i]) dis[i] = 0, dfs(i); 
  } 
  for (int i = 1; i <= N; i++) cout<<dis[i]<<" ";
  puts("");
  return 0;
}

原文地址：http://www.cnblogs.com/Dita/p/16923793.html