一道图论的综合题。
题目有几个要求。
首先,互相可到达的两个节点分在一起,用到强联通缩点。
然后可到达的分到一起。
用到最小路径覆盖。
代码如下:
#include<stdio.h> #include<string.h> #include<limits.h> #include<vector> using namespace std; const int mx1=5005; const int mx2=100005; int n,m,top,res,cnt,index; int low[mx1],dfn[mx1],vis[mx1]; int color[mx1],stack[mx1]; struct road //保存m条路的信息。为了第二次使用。 { int a,b; } r[mx2]; vector<int> vec[mx1]; struct node { int e,next; } edge[mx2]; int head[mx2]; int flag[mx1],match[mx1]; void add(int a,int b) { edge[res].e=b; edge[res].next=head[a]; head[a]=res++; } //初始化 void init() { top=index=res=cnt=0; for(int i=0; i<mx1; i++) { low[i]=dfn[i]=vis[i]=color[i]=0; vec[i].clear(); } memset(head,-1,sizeof(head)); } // 强联通缩点 int tarjan(int u) { low[u]=dfn[u]=++index; stack[top++]=u; vis[u]=1; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].e; if(!dfn[v]) { tarjan(v); low[u]=low[u]<low[v]?low[u]:low[v]; } else if(vis[v]&&dfn[v]<low[u]) low[u]=dfn[v]; } if(low[u]==dfn[u]) { cnt++; int v; do { v=stack[--top]; vis[v]=0; color[v]=cnt; //缩点的核心。 } while(v!=u); } } //最小路径覆盖。 int dfs(int u) { for(int i=0; i<vec[u].size(); i++) { int v=vec[u][i]; if(!flag[v]) { flag[v]=1; if(match[v]==-1||dfs(match[v])) { match[v]=u; return 1; } } } return 0; } int hun() { int sum=0; memset(match,-1,sizeof(match)); for(int i=1; i<=cnt; i++) { memset(flag,0,sizeof(flag)); if(dfs(i)) sum++; } return sum; } //数据处理。 void sove() { for(int i=1; i<=n; i++) { if(!dfn[i]) tarjan(i); } for(int i=0; i<m; i++) { int a=color[r[i].a]; int b=color[r[i].b]; if(a!=b) vec[a].push_back(b); } printf("%d\n",cnt-hun()); } int main() { int t; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d",&r[i].a,&r[i].b); add(r[i].a,r[i].b); } sove(); } return 0; }