第2回グリーンコンピュータ大会コード挑戦試合(第2段階C++図論題)

としどうろ
任務に挑戦する.
 A国の国土はいくつかの都市からなり、これらの都市はいくつかの島に分布し、都市の間はいくつかの双方向道路で接続され、互いにつながっている.一つの道が二つの島を越えたら、この道は橋です.今、A国の地図を持っています.地図にはA国のすべての都市と道路が表示されていますが、島は表示されていません.このうちA国の橋は、1つの道路を削除した後、2つの都市がつながっていない場合、この道路は橋に違いないという条件を満たしています.次の2つの質問に答えてください.

A国には全部で何本の橋がありますか.

いずれかの都市から他のいずれかの都市まで最大何本の橋を渡る必要があります.

に言及
  は1枚の連通の無方向図(重い辺がある)を与えて、すべての橋と任意の2点間の橋の数の最大値を求めます.  データ範囲:1<=n<=1 e 5 1<=m<=5 e 5
構想
ブリッジを求めてtarjanアルゴリズムは欠かせないが、何発か渡した後、そんなに簡単ではなく、テンプレートを直接セットすれば解決できるわけではないことに気づいた.全体の考え方:まずTarjanは2つの連通の縮点を結んで、更に橋を求めて、走りながら木の直径を走ります.O(n+m). 縮み点はリングを外し、木の直径を走るためです.第一に橋の数を求めて、いくつかのサンプルの答えが私より小さいことを発見して、とても退屈で、テンプレートは間違いなく問題がなくて、何か注意しなければならない点を考えて、このような可能性だけあって、私の答えは大きくて、重い辺が現れる時、その中の1つの重い辺を行って連通に影響しないで、テーマはきっとこの意味で、元のテンプレートは複数の重い辺が1つの辺だけを計算して、だから答えは大きくなります.どのように直すかは、結局、縮点が徹底的ではなく、重辺も一つの点に縮まなかったことだ.まず、重辺を見つけます:if(child=fa)num++で、numが重辺を持っていない場合は一般的に1です.これは双方向図なので、重辺があれば自然>1です.さらに縮点を行うと、以前のbelong配列では不十分で、判断が悪い.重辺がリングの真ん中に現れる可能性があるため、このときは気にしないで、橋に現れる可能性がある.

重辺は重辺に隣接する:すべての重辺は1つの点

に縮小する必要がある.

重辺はリングに隣接する:重辺はリングに1つの点

に縮小する.

重辺独立:この2点を1つの点

に縮小
元のテンプレートは十分ではなく、bccは1つのリングを見つけるたびに、つまり元のテンプレートの意味は各リングが1つの縮点であり、次の縮点は必ず異なり、bccは変化する(bccは現在どの縮点に属しているかを示す);これですべての問題を解決します.縮小点が解決した後、図を再構築し、tarjanを走ってすべての橋、木の直径を求めます.なぜ最後に木の直径を求めればいいのか、簡単です.縮んだ後、残りは木で、どの辺も橋です(実は新しい図がどれだけあるかを記録すれば橋がどれだけあるか(n-1)がわかりますが、大丈夫です.影響は大きくありません).だから、答えは木の上の2点の最長距離を求めれば、木の直径です.Tarjan複雑度はいずれもO(n+m)ツリーの直径2パスbfsでありO(n+m)であり,複雑度O(α\alpha αm)、総複雑度はO(n+α\alpha αm)、圧縮パスを調べるα\alpha αとても小さいです.具体的なアルゴリズムの詳細は説明せず,構想のみを提供する.
コード:

#ifndef __SOLVER_H__
#define __SOLVER_H__

#include 
using namespace std;
#define maxn 100005
#define maxm 1000005

int head[maxn], num, tov[maxm], nex[maxm], len[maxn];
int ff[maxn];
bool instack[maxn];
int low[maxn], dfn[maxn];//   
int sta[maxn], fa[maxn], fuben[maxn];// ，     ，               
int top, id, bcc;//  ，    ，         

class Solver
{
public:
    //   
	int find(int x)
	{
		return ff[x] == x ? x : ff[x] = find(ff[x]);
	}
	void add_edge(int from, int to, int dis)
	{
		nex[++num] = head[from];
		tov[num] = to;
		head[from] = num;
		len[num] = dis;
	}
	//      
	void tarjan1(int u, int fa)
	{
		int i;
		int num = 0;//    
		dfn[u] = low[u] = ++id;
		instack[u] = 1;
		sta[++top] = u;
		for (i = head[u]; i != -1; i = nex[i])
		{
			int v = tov[i];
			if (v == fa)
			{
				num++;
				continue;
			}
			if (!dfn[v])
			{
				tarjan1(v, u);
				low[u] = min(low[v], low[u]);
			}
			else if (instack[v])
				low[u] = min(dfn[v], low[u]);
		}

		if (num>1)//    
		{
			int x = find(u), y = find(fa);
			if (x != y)
				ff[x] = y;
		}

		if (dfn[u] == low[u])//    ，         ff[u]=u;
		{
			++bcc;
			int fu = find(u);
			do
			{
				i = sta[top--];
				int fv = find(i);
				if (fu != fv)
					ff[fv] = fu;
				instack[i] = 0;
			} while (i != u);
		}
	}

	int ind, ans1, ans2;
	void tarjan2(int cur, int fa)//cur     ，fa     
	{
		int child;
		dfn[cur] = ++ind;//          
		low[cur] = dfn[cur];//                      
		for (int i = head[cur]; i != -1; i = nex[i]) //  cur     
		{
			child = tov[i];
			if (dfn[child] && child != fa)
				low[cur] = min(low[cur], dfn[child]);//               ，  low  
			if (!dfn[child])//              
			{
				tarjan2(child, cur);//    dfs  

				if (dfn[cur]q;
		q.push(st);
		while (!q.empty())
		{
			int u = q.front();
			vis[u] = true;
			q.pop();
			for (int i = head[u]; i != -1; i = nex[i])
			{
				int v = tov[i], di = len[i];
				if (!vis[v])
				{
					dis[v] = dis[u] + di;
					q.push(v);
					if (dis[v]>Max)
					{
						Max = dis[v];
						t = v;
					}
				}
			}
		}
	}

	int get_max(int st)//  bfs     
	{
		bfs(st);
		bfs(t);
		return Max;
	}

	void init1()
	{
		memset(head, -1, sizeof(head));
		num = 0;
		memset(instack, 0, sizeof(instack));
		memset(low, 0, sizeof(low));
		memset(dfn, 0, sizeof(dfn));
		memset(sta, 0, sizeof(sta));
		memset(fa, 0, sizeof(fa));
		memset(fuben, 0, sizeof(fuben));
		top = 0, id = 0, bcc = 0;
	}

	void init2()
	{
		memset(head, -1, sizeof(head));
		num = 0;
		memset(low, 0, sizeof(low));
		memset(dfn, 0, sizeof(dfn));
		ind = 0;
		ans1 = 0, ans2 = 0;
		memset(dis, 0, sizeof(dis));
		memset(vis, 0, sizeof(vis));
	}
public:
	pair solve(int n, const vector > &edges)
	{
		/********** Begin **********/
		for (int i = 1; i <= n; i++)
			ff[i] = i;
		init1();
		for (int i = 0; ians = make_pair(ans1, ans2);
		return ans;
		/********** End **********/
	}
};

#endif

int main()
{
	int n, m;
	while (cin >> n >> m)
	{
		vector >edge;
		for (int i = 0; i> x >> y;
			edge.push_back(make_pair(x, y));
		}

		Solver sol;
		pair ans = sol.solve(n, edge);
		cout << ans.first << " " << ans.second << endl;
	}
	return 0;
}