首页 > 代码库 > 暑假集训day2
暑假集训day2
其实这是昨天的事了。(现在时间回到一天前)
今天的主要内容是强连通分量的割点与桥
一下给出割点和桥的写法
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<map> using namespace std; const int maxn=500010; int dfn[maxn],low[maxn],t=0,n,m,ans=0; bool cut[maxn]; vector<int>g[maxn]; inline int read(){ int num=0,t=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c<=‘9‘&&c>=‘0‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } void add(int x,int y){ g[x].push_back(y);g[y].push_back(x); } void tarjan(int x,int fa){ int child=0;dfn[x]=low[x]=++t; for(int i=0;i<g[x].size();i++){ int y=g[x][i];if(y==fa)continue; if(!dfn[y]){ child++; tarjan(y,x); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x])cut[x]=true; } else low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]&&fa!=-1)ans++; if(fa==-1&&child<=1)cut[x]=false; } int main() { n=read();m=read(); for(int i=1;i<=m;i++){ int x,y;x=read();y=read();add(x,y); } memset(dfn,0,sizeof(dfn));memset(cut,0,sizeof(cut)); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1); for(int i=1;i<=n;i++)if(cut[i])printf("%d ",i); puts("");printf("%d\n",ans); return 0; }
我还刷了一道水题
本题涉及到桶排序
挺简单的
题目:明明的随机数;见codevs1075
#include<iostream> #include<cstdio> using namespace std; int n,m,a[1010]={0}; int main() { cin>>n; for(int i=1;i<=n;i++){cin>>m;a[m]=1;} m=0; for(int i=1;i<=1000;i++)if(a[i])m++; cout<<m<<"\n"; for(int i=1;i<=1000;i++)if(a[i])cout<<i<<" "; return 0; }
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。
暑假集训day2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。