班長選挙-連通子図+縮点

タイトルの説明
大学のクラスは班長を選んで、N人の学友はすべて意見を発表することができて、もし意見がA BならばAはBが適切だと思って、意見は伝達性があって、つまりAはBが適切だと思って、BはCが適切だと思って、AもCが適切で勤勉なTTはM条の意見を集めて、最高の票数を知りたくて、そして候補者のリストを出して、つまりすべての得票が最も多い学友、あなたは彼を助けることができますか?
Input
この問題には複数のデータがあります.1行目Tは、データ群数を表す.各セットのデータは、2つの整数NおよびM(2<=n<=5000、0
Output
各グループのデータに対して、1行目は「Case x:」、xはデータの番号を表し、1から、最も高い票数が続く.次の行は得票が最も多い学生の番号を出力して、スペースで隔てて、行末のスペースを無視しません!
Sample Input
2 4 3 3 2 2 0 2 1
3 3 1 0 2 1 0 2
Sample Output
Case 1: 2 0 1 Case 2: 2 0 1 2
問題を解く構想.
本題と前の問題では感覚が違うのは、簡単そうに見えるかもしれませんが、実際によく考えてみると解決するのは難しいことに気づきます.この問題を見たばかりの頃、まずFloydアルゴリズムを用いることを考えた.このアルゴリズムは伝達性の問題を解決できるからだが、リングが存在する可能性があるという問題を考慮して、説明の中でこの方法に言及していないことを考慮して、しばらく放棄するか、それとも標準アルゴリズムを用いるか.まずdfsを用いて遍歴し、0点から図の後序シーケンスを見つけ、それから逆後序シーケンスを見つけた.このシーケンスに基づいて逆図を巡回し、各連通サブ図を見つけ、対応するタグを付けます.連通サブマップに基づいて縮点を行い,縮点後の原図と反図を得,原図に出度0の縮点を見つけ,縮点後の反図にこれらの点を起点としてdfs遍歴を行い,縮点後の重み値に基づいて経路が最も長い縮点を見つけ,最後の求め値である.
コード#コード#

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxm = 5010, maxn = 3e4 + 10;
int head1[maxm], head2[maxm], out_deg[maxm];//          
int vis[maxm], c[maxm];//c       scc ，vis       
int scc[maxm], scnt;//scc             ，scnt         
int dfn[maxm], dcnt;//            
int T, N, M, A, B;
int tot1 = 0, tot2 = 0;
int sh_vis[maxm];
int ans[maxm];
pair<int, int> a[maxm];//ans   
struct Edge
{
	int u, v, nxt;//   ，   ，  ，     
};
Edge e1[maxn], e2[maxn];//        
vector<int> sh_gra1[maxm], sh_gra2[maxm];//          
int temp = 0;
void addedge1(int u, int v)
{
	e1[tot1].u = u;
	e1[tot1].v = v;
	out_deg[u]++;
	e1[tot1].nxt = head1[u];
	head1[u] = tot1;
	tot1++;
}
void addedge2(int u, int v)
{
	e2[tot2].u = u;
	e2[tot2].v = v;
	e2[tot2].nxt = head2[u];
	head2[u] = tot2;
	tot2++;
}
void init()
{
	tot1 = tot2 = 0;
	dcnt = scnt = 0;
	temp = 0;
	for (int i = 0; i <= N; i++)
	{
		a[i].first = a[i].second = 0;
		head1[i] = -1;
		head2[i] = -1;
		out_deg[i] = 0;
		vis[i] = 0;
		scc[i] = 0;
		c[i] = 0;
		ans[i] = 0;
		while (sh_gra1[i].size()) sh_gra1[i].pop_back();
		while (sh_gra2[i].size()) sh_gra2[i].pop_back();
	}
}

void dfs1(int m)
{
	vis[m] = 1;
	for (int i = head1[m]; i != -1; i = e1[i].nxt)
		if (!vis[e1[i].v]) dfs1(e1[i].v);
	dfn[dcnt] = m;
	dcnt++;
}

void dfs2(int m)
{
	c[m] = scnt;
	scc[c[m]]++;//              
	for (int i = head2[m]; i != -1; i = e2[i].nxt)
		if (!c[e2[i].v]) dfs2(e2[i].v);
}

void get_shorted_graph()
{
	for (int i = 1; i <= N; i++)
		out_deg[i] = 0;
	for (int i = 0; i < N; i++)
		for (int j = head1[i]; j != -1; j = e1[j].nxt)
		{
			int y = e1[j].v;
			if (c[i] == c[y]) continue;
			sh_gra1[c[i]].push_back(c[y]);
			out_deg[c[i]]++;
			sh_gra2[c[y]].push_back(c[i]);//   
		}
}

void dfs3(int m)
{
	sh_vis[m] = 1;
	for (auto i : sh_gra2[m])
	{
		if (!sh_vis[i])
		{
			ans[temp] += scc[i];
			dfs3(i);
		}
	}
}
bool cmp(pair<int, int>a, pair<int, int>b)
{
	return a.first > b.first;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> N >> M;
		init();
		for (int j = 0; j < M; j++)
		{
			cin >> A >> B;
			addedge1(A, B);
			addedge2(B, A);//   
		}
		for (int j = 0; j < N; j++)
			if (!vis[j]) dfs1(j);
		for (int j = dcnt - 1; j >= 0; j--)
			if (!c[dfn[j]])
			{
				scnt++;
				dfs2(dfn[j]);
			}
		get_shorted_graph(); //       
		vector<int> zero_outd;
		for (int j = 1; j <= scnt; j++)
			if (!out_deg[j]) zero_outd.push_back(j);
		int s = zero_outd.size();
		for (int j = 0; j < s; j++)
		{
			memset(sh_vis, 0, sizeof sh_vis);
			ans[temp] += scc[zero_outd[j]] - 1;
			dfs3(zero_outd[j]);

			a[temp].first = ans[temp];
			a[temp].second = zero_outd[j];
			temp++;
		}
		while (zero_outd.size()) zero_outd.pop_back();
		sort(a, a + s, cmp);
		cout << "Case " << i + 1 << ": " << a[0].first << endl;
		priority_queue<pair<int, int> > w;
		pair<int, int> r;
		int h = 0;
		for (int j = 0; j < s; j++)
		{
			h = 0;
			if (a[j].first == a[0].first)
			{
				for (int u = 0; u < N; u++)
				{
					if (c[u] == a[j].second) w.push(make_pair(-u, u)), h++;
					if (h == scc[c[u]]) break;
				}
			}
		}
		while (w.size() > 1)
		{
			cout << w.top().second << " ";
			w.pop();
		}
		cout << w.top().second;
		cout << endl;
	}
	return 0;
}