只存代码
T1
并查集
#include<bits/stdc++.h>
using namespace std;
int f[200001],a,e[200001];
int fin(int x)
{
if(f[x]!=x)
{
int last=f[x];
f[x]=fin(f[x]);
e[x]+=e[last];
}
return f[x];
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)
f[i]=i;
int minn=0x3fffff;
for(int i=1;i<=n;++i)
{
cin>>a;
int x=fin(i);
int y=fin(a);
if(x!=y)
{
f[x]=y;
e[i]=e[a]+1;
}
else
minn=min(minn,e[i]+e[a]+1);
}
cout<<minn;
}
T2
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,m;
vector <int> t[maxn];
int dfn[maxn],low[maxn],tot;
int stk[maxn],instk[maxn],top;
int scc[maxn],divs[maxn],cnt;
int dout[maxn];
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
stk[++top]=x,instk[x]=1;
for(int y: t[x])
{
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(instk[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
int y;++cnt;
do
{
y=stk[top--];
instk[y]=0;
scc[y]=cnt;
++divs[cnt];
}while(y!=x);
}
}
int main()
{
cin>>n>>m;
int a,b;
while(m--)
{
cin>>a>>b;
t[a].push_back(b);
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
for(int x=1;x<=n;++x)
for(int y : t[x])
if(scc[x]!=scc[y])
++dout[scc[x]];
int sum=0,zer=0;
for(int i=1;i<=cnt;++i)
if(dout[i]==0)
{
sum=divs[i];
++zer;
}
if(zer>1) sum=0;
cout<<sum<<endl;
}
T3
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500010;
struct node
{
int v,next;
}e[N],maps[N];
int n,m;
int st[N],head[N],cnt;
int atm[N],money[N];
int d[N],q[N];
void bulid(int a,int b)
{
e[++cnt].v=b;
e[cnt].next=st[a];
st[a]=cnt;
}
int sta[N],top;
int dfn[N],low[N],dex;
bool vis[N];
int color[N],num;
void tarjan(int x)
{
dfn[x]=++dex;
low[x]=dex;
vis[x]=1;
sta[++top]=x;
for(int i=st[x];i!=0;i=e[i].next)
{
int temp=e[i].v;
if(!dfn[temp])
{
tarjan(temp);
low[x]=min(low[x],low[temp]);
}
else if(vis[temp]) low[x]=min(low[x],dfn[temp]);
}
if(dfn[x]==low[x])
{
vis[x]=0;
color[x]=++num;
while(sta[top]!=x)
{
color[sta[top]]=num;
vis[sta[top--]]=0;
}
top--;
}
}
void add()
{
cnt=0;
for(int i=1;i<=n;++i)
for(int j=st[i];j!=0;j=e[j].next)
{
int temp=e[j].v;
if(color[i]!=color[temp])
{
maps[++cnt].v=color[temp];
maps[cnt].next=head[color[i]];
head[color[i]]=cnt;
}
}
}
void spfa(int x)
{
memset(vis,0,sizeof(vis));
int l=1,r=1;
q[l]=x;
vis[x]=1;
d[x]=money[x];
while(l<=r)
{
int u=q[l++];
for(int i=head[u];i!=0;i=maps[i].next)
{
int v=maps[i].v;
if(d[v]<d[u]+money[v])
{
d[v]=d[u]+money[v];
if(vis[v]) continue;
q[++r]=v;
vis[v]=1;
}
}
vis[u]=0;
}
}
signed main()
{
int a,b,i,s,p,o,ans=0;
cin>>n>>m;
for(int i=1;i<=m;++i)
{
cin>>a>>b;
bulid(a,b);
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
add();
for(int i=1;i<=n;++i)
{
cin>>atm[i];
money[color[i]]+=atm[i];
}
cin>>s>>p;
spfa(color[s]);
for(int i=1;i<=p;++i)
{
cin>>o;
ans=max(ans,d[color[o]]);
}
cout<<ans;
}
T4
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500010;
vector<int> a[N];
int n,root,num(0),ans(0),low[101],dfn[101];
bool f[101]={0};
void add(int t1,int t2)
{
a[t1].push_back(t2);
a[t2].push_back(t1);
return;
}
void tarjan(int t)
{
int sum(0);
low[t]=dfn[t]=++num;
for(int i=0;i<a[t].size();++i)
{
int T=a[t][i];
if(!dfn[T])
{
tarjan(T);
sum++;
low[t]=min(low[t],low[T]);
if((t==root && sum>1) || (t!=root && low[T]>=dfn[t]))
{
if(!f[t])
ans++,f[t]=1;
}
//找割点
}
else low[t]=min(low[t],dfn[T]);
}
return ;
}
signed main()
{
cin>>n;
int t1,t2;
while (scanf("%lld%lld",&t1,&t2)!=EOF)
add(t1,t2);
for(int i=1;i<=n;++i)
if(!dfn[i])
{
root=i;
tarjan(i);
}
cout<<ans<<endl;
for(int i=1;i<=n;++i)
if(f[i])
cout<<i<<endl;
}