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;
}