题意:
给n个点m条有向边。求出满足这个条件的最小集合数量:该集合内任意两个点相互之间不能直接或间接到达。也就是说 这个集合内的任意两个点都没有关系。
输出满足这个条件的最小集合数
思路:
首先将强连通分量缩点。该缩点的点权为点的个数。因为强连通分量中任意两个点都有直接或者间接关系。
缩点后重新建图。
然后对新图拓扑排序求最长链。
拓扑排序的三个步骤(队列实现):
1)将入度为0的点放入队列中
2)从队列中取出点,将其边指向的下一个点的入度-1
3)重复1)、2)的步骤直到队列为空
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> using namespace std; #define MAXN 100010 vector <int> e[MAXN]; vector <int> e1[MAXN]; int dfn[MAXN],low[MAXN],bleg[MAXN],sta[MAXN]; int times,top,n,m; void tarjan(int u){ dfn[u]=low[u]=++times; sta[++top]=u; for(int i=0;i<(int)e[u].size();i++){ int v=e[u][i]; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(!bleg[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]){ bleg[0]++; do { bleg[sta[top]]=bleg[0]; } while (sta[top--]!=u); } } void init(){ memset(dfn,0,sizeof(dfn)); memset(bleg,0,sizeof(bleg)); top=times=0; } int vis[MAXN]; int vv[MAXN]; int ru[MAXN]; queue <int> q; int bfs(){ while(!q.empty())q.pop(); for(int i=1;i<=bleg[0];i++){ if(ru[i]==0){ q.push(i); vis[i]=vv[i]; } else vis[i]=0; } int mm=0; while(!q.empty()){ int now=q.front(); q.pop(); if(vis[now]>mm)mm=vis[now]; for(int i=0;i<(int)e1[now].size();i++){ int next=e1[now][i]; vis[next]=max(vis[next],vis[now]+vv[next]); ru[next]--; if(ru[next]==0) q.push(next); } } return mm; } int main() { while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n+10;i++)e[i].clear(); for(int i=0;i<n+10;i++)e1[i].clear(); for(int i=0;i<n+10;i++)vv[i]=0; for(int i=0;i<m;i++){ int x,y; scanf("%d%d",&x,&y); e[x].push_back(y); } init(); for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); memset(ru,0,sizeof(ru)); for(int i=1;i<=n;i++){ ++vv[bleg[i]]; for(int j=0;j<(int)e[i].size();j++){ int v=e[i][j]; if(bleg[i]==bleg[v])continue; e1[bleg[i]].push_back(bleg[v]); ++ru[bleg[v]]; } } printf("%d\n",bfs()); } return 0; }
|