C bomb(tarjin + 拓扑排序)

C-Problem C. bomb_2021 CCPC 新疆省赛（重现赛）@Joanh_Lan (nowcoder.com)

潇湘有一个有向图，有n个点和m条边。起初，有向图上的每个点都是白色的。最近，潇湘想把这个有向图上的每个点都涂成黑色。他可以进行几轮染色，每轮的染色规则如下:在每一轮染色中，潇湘可以染任意数量的点。在每个染色回合中，一对不同的i, j不能出现，让i点可以到达j点。现在，潇湘想让你计算一下，这个有向图上的每个点至少要经过几轮染色才能被染色。

第一行中的两个正整数n,m表示这个有向图的点和边的个数。其中点的个数为1~n。下m行，每一行有两个正整数æ，y，表示有一条有向边从x连接到y。2 < n < 1,010米< 10°

输入

复制

5 4
1 2
2 3
3 1
4 5

输出

复制

3

题解:
本题没思路的最大原因还是题意给的不够清楚.

每轮的染色规则如下:在每一轮染色中，潇湘可以染任意数量的点。在每个染色回合中，一对不同的i, j不能出现，让i点可以到达j点。

首先,注意一轮可以染任意数量的点,其次(在一轮中的点,不能出现i可以到j)

在理清题意后本题就好写了

1.首先我们考虑无环的情况下,

答案应该是他最长链的长度,因为任何时候我们都不能选同一条链上的两个点或两点以上

2.其次我们考虑有环的情况下,

对于环上的点,我们一次只能染一个点,因为环上任意两个点都可以相互到达

那我们就tarjin缩一下点,的得到无环图,再利用拓扑排序,求出最长链即可

所以说,理清题意真的很重要QAQ

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
//#define int long long
typedef pair<int,int> PII;
const int N = 1e6 + 10;
int e[N],h[N],ne[N],idx;
int n,m;
int siz[N];
int dfn[N],low[N];
int vis[N];
int col[N];
int stk[N];
int top;
void add(int l,int r)
{
	e[idx] = r;
	ne[idx] = h[l];
	h[l] = idx++;
}
int cnt;
int id;
void tarjin(int u)
{
	dfn[u] = low[u] = ++cnt;
	stk[++top] = u;
	vis[u] = 1;
	for(int i = h[u]; i != -1;i = ne[i])
	{
		int v = e[i];
		if(!dfn[v])
		{
			tarjin(v);
			low[u] = min(low[u],low[v]);
		}
		else if(vis[v])
		{
			low[u] = min(low[u],dfn[v]);
		}
	}
	if(dfn[u] == low[u])
	{
		id ++;
		int x;
		do{
			x = stk[top--];
			vis[x] = 0;
			col[x] = id;
			siz[id] ++;
		}while(x != u);
	} 
} 
int h1[N],e1[N],ne1[N],idx1;
int du[N];
int dis[N];
void add1(int l,int r)
{
	e1[idx1] = r;
	ne1[idx1] = h1[l];
	h1[l] = idx1++;
	du[r]++;
}

void topu()
{
	queue<int> q;
	for(int i = 1;i <= id;i++)
	{
		if(du[i] == 0)
		{
			q.push(i);
			dis[i] = siz[i];
		}
	}
	while(q.size())
	{
		int u = q.front();
		q.pop();
		for(int i = h1[u];i != -1;i = ne1[i])
		{
			int v = e1[i];
			dis[v] = max(dis[v], dis[u] + siz[v]);
			if(--du[v] == 0)
			{
				q.push(v);
			}
		}
	}
}
void solve()
{
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	memset(h1,-1,sizeof h1);
	for(int i = 1;i <= m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	for(int i = 1;i <= n;i++)
	{
		if(!dfn[i])
		{
			tarjin(i);
		}
	}
	for(int i = 1;i <= n;i++)
	{
		for(int k = h[i];k != -1;k = ne[k])
		{
			int j = e[k];
			if(col[i] == col[j])
			continue;
			add1(col[i],col[j]);
		}
	}
	topu();
	int ans = 0;
	for(int i = 1;i <= id;i ++)
	{
		ans = max(ans,dis[i]);
	}
	cout << ans;
}
signed main() 
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
//    scanf("%lld",&t);
	while (t--) 
	{
		solve();
	}
	return 0;
}