普洱市网站建设,cms 免费,牙科网站建设,wordpress文章宽度自适应正题
题目链接 大意
有n头奶牛#xff0c;奶牛们会认为有些奶牛很受欢迎#xff0c;受欢迎会互相传递#xff0c;如:如果A认为B很受欢迎#xff0c;而B认为C受欢迎#xff0c;那么A也会认为C是受欢迎的。然后求每一个奶牛都认为受欢迎的奶牛数量。 解题思路
先用tarjan…正题
题目链接 大意
有n头奶牛奶牛们会认为有些奶牛很受欢迎受欢迎会互相传递如:如果A认为B很受欢迎而B认为C受欢迎那么A也会认为C是受欢迎的。然后求每一个奶牛都认为受欢迎的奶牛数量。 解题思路
先用tarjan算法算一遍联通分量然后如果该联通分量出度为0且是唯一一个为0的那么这个强联通分量里就是受每个奶牛欢迎的。
讲解一下原理 首先我们假设这道题有解那么我们将每一个强联通分量看做一个整体然后如果该整体有出度那么说明这不是最受欢迎的因为如果受到出度链接的那个整体欢迎的话那么就应该是一个联通分量里的。如果有两个出度为0那么这两个整体就不会互相喜欢就无解。 代码
#includecstdio
#includestack
using namespace std;
stackint Stack;
struct line{int h,t,next;
};
int n,m,dfn[10001],low[10001],stn,ls[10001],ltn,lt[10001];
int ltm[10001],wr[10001],s1,ans;
bool instack[10001];
line a[50001];
void tarjan(int x)
{dfn[x]low[x]stn;instack[x]true;Stack.push(x);//入栈int y;for (int qls[x];q;qa[q].next)//枚举连接到{ya[q].t;if (!dfn[y])//如果没用计算{tarjan(y);//计算low[x]min(low[x],low[y]);//更新low值}else if (instack[y] low[x]dfn[y])low[x]dfn[y];}if (dfn[x]low[x]){ltn;while (Stack.size()0){yStack.top();Stack.pop();ltm[ltn];lt[y]ltn;if (yx) break;}//归入同一个强连通分量}
}
int main()
{scanf(%d%d,n,m);for (int i1;im;i){scanf(%d%d,a[i].h,a[i].t);a[i].nextls[a[i].h];ls[a[i].h]i;}for (int i1;in;i)if (dfn[i]0) tarjan(i);//跑一遍for (int i1;im;i)if (lt[a[i].t]!lt[a[i].h]){wr[lt[a[i].h]];}//计算每个强连通的出度for (int i1;iltn;i)if (!wr[i]){ansi;s1;//计算出度为0的数量}if (s11) printf(%d,ltm[ans]);else printf(0);
}
