题意:有N个牛,围在一水池边,它们用绳子互相绑着(有方向的)。如果绳子的方向一致,它们就能顺时针转,问有多少组牛可以跳舞。
思路:简单有向图的强连通分量。求出强连通分量,且强连通分量里的点数大于等于2的块就能跳舞。
//836K 79MS #include #include #include using namespace std; const int VM = 10005; const int EM = 50005; struct Edge { int to,nxt; }edge[EM]; int head[VM],vis[VM],dfn[VM],low[VM]; int stack[VM+10],belong[VM]; int scc,cnt,top,ep; void addedge (int cu,int cv) { edge[ep].to = cv; edge[ep].nxt = head[cu]; head[cu] = ep++; } int min (int a ,int b) { return a > b ? b : a; } void Tarjan(int u) { dfn[u] = low[u] = ++cnt; vis[u] = 1; stack[top++] = u; int v; for (int i = head[u];i != -1;i = edge[i].nxt) { v = edge[i].to; if (!dfn[v]) { Tarjan(v); low[u] = min(low[u],low[v]); } else if (vis[v]) low[u] = min(low[u],dfn[v]); } if (dfn[u] == low[u]) { ++scc; do{ v = stack[--top]; vis[v] = 0; belong[v] = scc; }while (u != v); } } void solve(int n) { memset (vis,0,sizeof(vis)); memset (dfn,0,sizeof(dfn)); scc = cnt = top = 0; int u,v; for (u = 1;u <= n;u ++) if (!dfn[u]) Tarjan(u); sort (belong+1,belong+n+1); belong[n+1] = -1; // for (int i = 0;i <= n;i ++) // printf ("%d ",belong[i]); int pre = belong[1]; cnt = 0; int ans = 0; for (int i = 1;i <= n+1;i ++) { if (pre == belong[i]) ++cnt; else { pre = belong[i]; if (cnt >= 2) ans ++; cnt = 1; } } printf ("%d\n",ans); } int main () { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int n,m,u,v; while (~scanf ("%d%d",&n,&m)) { memset (head,-1,sizeof(head)); ep = 0; while (m --) { scanf ("%d%d",&u,&v); addedge (u,v); } solve(n); } return 0; }