和田地网站seo,网络营销和传统营销的区别,全栈工程师是做网站吗,天津做优化的网站有多少家时间限制: 1 s空间限制: 128000 KB题目等级 : 钻石 Diamond题目描述 Description“每个人都拥有一个梦#xff0c;即使彼此不相同#xff0c;能够与你分享#xff0c;无论失败成功都会感动。爱因为在心中#xff0c;平凡而不平庸#xff0c;世界就像迷宫#xff0c;却又让… 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description “每个人都拥有一个梦即使彼此不相同能够与你分享无论失败成功都会感动。爱因为在心中平凡而不平庸世界就像迷宫却又让我们此刻相逢Our Home。” 在爱的国度里有N个人在他们的心中都有着一个爱的名单上面记载着他所爱的人不会出现自爱的情况。爱是具有传递性的即如果A爱BB爱C则A也爱C。如果有这样一部分人他们彼此都相爱则他们就超越了一切的限制用集体的爱化身成为一个爱心天使。现在我们想知道在这个爱的国度里会出现多少爱心天使。而且如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的否则输出-1。 输入描述 Input Description 第1行两个数N、M代表爱的国度里有N个人爱的关系有M条。第2到第M1行每行两个数A、B代表A爱B。 输出描述 Output Description 第1行一个数代表爱的国度里有多少爱心天使。第2行如果某个爱心天使被其他所有人和爱心天使所爱则请输出这个爱心天使是由哪些人构成的从小到大排序否则输出-1。 样例输入 Sample Input 样例输入1 6 71 22 33 24 24 55 66 4 样例输入2 3 31 22 12 3 样例输出 Sample Output 样例输出1 22 3 样例输出2 1-1 数据范围及提示 Data Size Hint 各个测试点1s Tarjan缩点、求强连通分量重新构图 被其他所有人爱 也就是入度等于强连通分量数-1 间接被爱也需要统计 我用的是floyd 略慢大佬们可改进 (大佬们肯定不会路过。。)。 注意图可能不连通 屠龙宝刀点击就送 #include ctype.h
#include cstdio
#define N 100005void read(int x)
{x0;bool f0;register char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) f1;for(;isdigit(ch);chgetchar()) xx*10ch-0;xf?(~x)1:x;
}
struct Edge
{int next,to;Edge (int next0,int to0) :next(next),to(to){}
};
struct Edge edge[N1];
int Map[300][300],in[N],newhead[N],tim,head[N],num[N],cnt,n,m,dfn[N],low[N],sumcol,col[N],stack[N],top;
bool instack[N],flag;
int min(int a,int b){return ab?b:a;}
void tarjan(int x)
{low[x]dfn[x]tim;instack[x]1;stack[top]x;for(int uhead[x];u;uedge[u].next){int vedge[u].to;if(!dfn[v]){tarjan(v);low[x]min(low[x],low[v]);}else if(instack[v]) low[x]min(low[x],dfn[v]);}if(low[x]dfn[x]){sumcol;int t;do{tstack[top--];instack[t]false;col[t]sumcol;num[sumcol];}while(t!x);}
}
void rebuild()
{for(int i1;in;i){for(int uhead[i];u;uedge[u].next){int vedge[u].to;if(col[i]!col[v]!Map[col[i]][col[v]]){Map[col[i]][col[v]]1;in[col[v]];}}}for(int i1;isumcol;i){for(int j1;jsumcol;j){for(int k1;ksumcol;k){if(j!kk!ii!j){if(Map[j][i]Map[i][k]!Map[j][k]){Map[j][k]1;in[k];}}}}}
}
int main()
{read(n);read(m);for(int x,y;m--;){read(x);read(y);edge[cnt]Edge(head[x],y);head[x]cnt;}for(int i1;in;i) if(!dfn[i]) tarjan(i);int ans0;for(int i1;isumcol;i) if(num[i]1) ans;printf(%d\n,ans);rebuild();for(int i1;isumcol;i){if(in[i]sumcol-1num[i]1) {for(int j1;jn;j)if(col[j]i) printf(%d ,j);printf(\n);flagtrue;}}if(!flag) printf(-1);return 0;
} 转载于:https://www.cnblogs.com/ruojisun/p/7204294.html
