「重庆联考2017D1T2」轰炸 - 缩点+最长链

题目大意

    战狂也在玩《魔方王国》。他只会征兵而不会建城市，因此他决定对小奇的城市进行轰炸。
    小奇有$n$座城市，城市之间建立了$m$条有向的地下通道。战狂会发起若干轮轰炸，每轮可以轰炸任意多个城市。
    每座城市里都有战狂部署的间谍，在城市遭遇轰炸时，它们会通过地下通道撤离至其它城市。非常不幸的是，在地道里无法得知其它城市是否被轰炸，如果存在两个不同的城市$i$，$j$，它们在同一轮被轰炸，并且可以通过地道从城市$i$到达城市$j$，那么城市$i$的间谍可能因为撤离到城市$j$而被炸死。为了避免这一情况，战狂不会在同一轮轰炸城市$i$和城市$j$。注意：炸毁的城市还是能够到达的。
    你需要求出战狂最少需要多少轮可以对每座城市都进行至少一次轰炸

---

题目分析

这是一道错题！
加入有一个四元环，答案应该是$3$而不是$4$！

然后xinyue表示不能拆分改变连通性。

注意相连是直接或间接相连，因此在同一个连通块的点只能一个一个删。
这就是一个裸的缩点+DAG最长链了，拓扑排序解决。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

int max(int a,int b) {
	if(a>b)return a;
	return b;
}

const int maxn=1000005;
int n,m,step=0,Ans=0,InDegree[maxn],f[maxn],Size[maxn],Dfn[maxn],Lowlink[maxn],Stack[maxn],top=0,Instack[maxn],father[maxn],Belong[maxn],SCC=0;
vector<int>edges[maxn],edges2[maxn];

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

void AddEdge2(int x,int y) {
	edges2[x].push_back(y);
	InDegree[y]++;
}

void Tarjan(int Now) {
	step++;
	Lowlink[Now]=Dfn[Now]=step;
	Stack[++top]=Now;
	Instack[Now]=1;
	for(int i=0; i<edges[Now].size(); i++) {
		int Next=edges[Now][i];
		if(!Dfn[Next]) {
			Tarjan(Next);
			Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
		} else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
	}
	if(Lowlink[Now]==Dfn[Now]) {
		SCC++;
		int y;
		do {
			y=Stack[top--];
			Belong[y]=SCC;
			Instack[y]=0;
			Size[SCC]++;
		} while(y!=Now);
	}
}

void Top_Sort() {
	queue<int>Q;
	for(int i=1; i<=SCC; i++)
		if(InDegree[i]==0)Q.push(i),f[i]=Size[i];
	while(!Q.empty()) {
		int Now=Q.front();
		Ans=max(Ans,f[Now]);
		Q.pop();
		for(int i=0; i<edges2[Now].size(); i++) {
			int Next=edges2[Now][i];
			InDegree[Next]--;
			f[Next]=max(f[Next],f[Now]+Size[Next]);
			Ans=max(Ans,f[Next]);
			if(!InDegree[Next])Q.push(Next);
		}
	}
}

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(x,y);
	}
	for(int i=1; i<=n; i++)
		if(!Dfn[i])Tarjan(i);
	for(int Now=1; Now<=n; Now++)
		for(int i=0; i<edges[Now].size(); i++) {
			int Next=edges[Now][i];
			if(Belong[Now]==Belong[Next])continue;
			AddEdge2(Belong[Now],Belong[Next]);
		}
	Top_Sort();
	printf("%d\n",Ans);
	return 0;
}