题意：给出n个点,m条有向边，问构造一个新图，最少几条边可以让任意两点间的连通性跟原图一样。做法：首先做出强连通分量，，很显然对于有向图而言，若分图的点不唯一必定成环，当然啦，还需要做的是把这些分图再连起来变成弱连通分量，若某个弱连通分量的点数为v，若有环则贡献v条边，否则贡献v-1条边。
#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<iostream>#include<algorithm>#include<bitset>#include<climits>#include<list>#include<iomanip>#include<stack>#include<set>using namespace std;stack<int>sk;bool insk[100010],isok[100010];int step,dfn[100010],low[100010],belong[100010],num[100010],tol;struct Edge{int to,next;}edge[200010];int head[100010],tail;void add(int from,int to){edge[tail].to=to;edge[tail].next=head[from];head[from]=tail++;}void dfs(int from){dfn[from]=low[from]=++step;sk.push(from);insk[from]=1;for(int i=head[from];i!=-1;i=edge[i].next){int to=edge[i].to;if(dfn[to]==0){dfs(to);low[from]=min(low[from],low[to]);}else if(insk[to])low[from]=min(low[from],dfn[to]);}if(dfn[from]==low[from]){int v;do{v=sk.top();sk.pop();insk[v]=0;belong[v]=tol;num[tol]++;}while(v!=from);if(num[tol]>1)isok[tol]=1;tol++;}}int pr[100010];int seek(int v){return pr[v]=v==pr[v]?v:seek(pr[v]);}int main(){int n,m;cin>>n>>m;memset(head,-1,sizeof(head));while(m–){int a,b;cin>>a>>b;add(a,b);}for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);for(int i=0;i<tol;i++)pr[i]=i;int ans=0;for(int i=1;i<=n;i++)for(int j=head[i];j!=-1;j=edge[j].next){int a=belong[i],b=belong[edge[j].to];a=seek(a);b=seek(b);if(a!=b){isok[a]|=isok[b];num[a]+=num[b];pr[b]=a;}}for(int i=0;i<tol;i++)if(pr[i]==i)ans+=num[i]+(isok[i]?0:-1);cout<<ans;}
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Shuseki Kingdom is the world’s leading nation for innovation and technology. There arencities in the kingdom, numbered from1ton.
Thanks to Mr. Kitayuta’s research, it has finally become possible to construct teleportation pipes between two cities. A teleportation pipe will connect two cities unidirectionally, that is, a teleportation pipe from cityxto cityycannot be used to travel from cityyto cityx. The transportation within each city is extremely developed, therefore if a pipe from cityxto cityyand a pipe from cityyto cityzare both constructed, people will be able to travel from cityxto cityzinstantly.
Mr. Kitayuta is also involved in national politics. He considers that the transportation between thempairs of city(ai,bi)(1≤i≤m) is important. He is planning to construct teleportation pipes so that for each important pair(ai,bi), it will be possible to travel from cityaito citybiby using one or more teleportation pipes (but not necessarily from citybito cityai). Find the minimum number of teleportation pipes that need to be constructed. So far, no teleportation pipe has been constructed, and there is no other effective transportation between cities.
Input
The first line contains two space-separated integersnandm(2≤n≤105,1≤m≤105), denoting the number of the cities in Shuseki Kingdom and the number of the important pairs, respectively.
The followingmlines describe the important pairs. Thei-th of them (1≤i≤m) contains two space-separated integersaiandbi(1≤ai,bi≤n,ai≠bi), denoting that it must be possible to travel from cityaito citybiby using one or more teleportation pipes (but not necessarily from citybito cityai). It is guaranteed that all pairs(ai,bi)are distinct.
Output
Print the minimum required number of teleportation pipes to fulfill Mr. Kitayuta’s purpose.
Sample test(s)
input
4 51 21 31 42 32 4
output
3
input
4 61 21 42 32 43 23 4
output
4
Note
路遥知马力，日久见人心。
