乌克兰服装网站建设,wordpress伪静态 文件夹,goggle营销型网站效果,深圳网络seo推广题目描述
有nnn座城市#xff0c;城市之间建立了mmm条有向的地下通道。
你需要发起若干轮轰炸#xff0c;每轮可以轰炸任意多的城市。但在每次轰炸城市中#xff0c;不能同时存在两个城市i,ji,ji,j满足可以通过地下通道从城市iii到达城市jjj。你需要求出最少需要多少轮可以…题目描述
有nnn座城市城市之间建立了mmm条有向的地下通道。
你需要发起若干轮轰炸每轮可以轰炸任意多的城市。但在每次轰炸城市中不能同时存在两个城市i,ji,ji,j满足可以通过地下通道从城市iii到达城市jjj。你需要求出最少需要多少轮可以对每座城市都进行至少一次轰炸。
输入格式
第一行一个整数mmm接下来mmm行每行两个整数a,ba,ba,b表示一条从aaa到bbb的单向边。
输出格式
一行一个整数表示答案。
样例输入
5 4
1 2
2 3
3 1
4 5样例输出
3数据范围
1≤n,m≤1061\leq n,m\leq 10^61≤n,m≤106 题解
题意即为每次可以轰炸任意多的城市但不能有两个城市i,ji,ji,j满足i,ji,ji,j在同一条链上。
如果这个图没有环那么显然答案为最长的一条链。这条链上每个点都轰炸一次。与此同时其他链上的点也都轰炸一次即可将所有城市都轰炸一次。用拓扑排序即可解决。
那如果有环呢我们可以用求强连通分量的Tarjan算法求出每个强连通分量再把每个强连通分量都缩成一个点。此时的图已经没有环了按上面的方法做就行了。
注意缩点之后炸完一个点所需要的次数为这个点表示的强连通分量的大小。
时间复杂度为O(n)O(n)O(n)。
code
#includebits/stdc.h
using namespace std;
const int N1000000;
int n,m,x,y,tot0,dt0,top0,ans0,d[N5],l[N5],r[N5],st[N5];
int ct0,dfn[N5],low[N5],c[N5],cnt[N5],f[N5];
vectorinthv[N5];
queueintq;
struct node{int x,y;
}w[N5];
void add(int xx,int yy){l[tot]r[xx];d[tot]yy;r[xx]tot;
}
void dfs(int u){dfn[u]low[u]dt;st[top]u;for(int ir[u];i;il[i]){int vd[i];if(!dfn[v]){dfs(v);low[u]min(low[u],low[v]);}else if(!c[v]){low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){ct;while(top0){c[st[top]]ct;hv[ct].push_back(st[top]);--top;if(st[top1]u) break;}}
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d,x,y);w[i](node){x,y};add(x,y);}for(int i1;in;i){if(!dfn[i]) dfs(i);}tot0;memset(r,0,sizeof(r));for(int i1;im;i){xw[i].x;yw[i].y;if(c[x]c[y]) continue;add(c[x],c[y]);cnt[c[y]];}for(int i1;ict;i){if(!cnt[i]) q.push(i);}while(!q.empty()){int uq.front();q.pop();f[u]hv[u].size();for(int ir[u];i;il[i]){f[d[i]]max(f[d[i]],f[u]);--cnt[d[i]];if(!cnt[d[i]]) q.push(d[i]);}}for(int i1;ict;i){ansmax(ans,f[i]);}printf(%d,ans);return 0;
}
