xiuzhiyuan

$$\href{https://www.acwing.com/blog/content/14845/}{\Huge\color{blue}{题解主页}}$$

6.3万

Eason_Y
zhan666nb
ACWING-XZY

yxc的小迷妹

23计科新生

ohhhdddentist
CLUANY
Acwer

QY琰

od2020
perfectionist
Finn2009

#include<iostream>
#include<cstring>
using namespace std;
const int N=2010,M=1000010;
int n,m;
bool stop[N];
int to[M],ne[M],w[M],h[N],idx=1;
int din[N];
int top[N];
int dist[N];
inline void add(int a,int b,int c){
to[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++,din[b]++;
}
inline void topsort(){
int hh=1,tt=1;
for(int i=1;i<=n+m;i++)
if(!din[i])
top[tt++]=i;
while(hh<tt){
int x=top[hh++];
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(--din[y]==0)
top[tt++]=y;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
memset(stop,0,sizeof stop);
int s,from,to;
scanf("%d",&s);
for(int i=1;i<=s;i++){
int x;
scanf("%d",&x);
stop[x]=1;
if(i==1)
from=x;
if(i==s)
to=x;
}
int mid=n+i;
for(int j=from;j<=to;j++)
if(stop[j])
else
}
topsort();
for(int i=1;i<=n;i++)
dist[i]=1;
for(int i=1;i<=n+m;i++){
int x=top[i];
for(int j=h[x];j;j=ne[j]){
int y=to[j];
dist[y]=max(dist[y],dist[x]+w[j]);
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dist[i]);
printf("%d",ans);
return 0;
}


#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned long long ULL;
const int N=1010;
int to[N],ne[N],h[N],idx;
int low[N],dft[N],nowt;
int s[N],tt;
int root;
bool ic[N]; //记录该点是否为割点
vector<int> bs[N];
int bcnt;
to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){
dft[x]=low[x]=++nowt;
s[++tt]=x;
if(!h[x]){
bcnt++;
bs[bcnt].push_back(x);
return;
}
int cnt=0;
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(!dft[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dft[x]<=low[y]){
cnt++;
if(x!=root||cnt>1)
ic[x]=1;
++bcnt;
do{
bs[bcnt].push_back(s[tt]);
}while(s[tt--]!=y);
bs[bcnt].push_back(x);
}
}
else
low[x]=min(low[x],dft[y]);
}
}
int main(){
int t=0,m;
while(scanf("%d",&m),m){
memset(h,0,sizeof h);
memset(ic,0,sizeof ic);
memset(dft,0,sizeof dft);
for(int i=1;i<=bcnt;i++)
bs[i].clear();
idx=1;
nowt=bcnt=0;
int n=0;
while(m--){
int a,b;
scanf("%d%d",&a,&b);
n=max(n,a);
n=max(n,b);
}
for(root=1;root<=n;root++)
if(!dft[root])
tarjan(root);
int ans1=0; //记录最少出口数
ULL ans2=1; //记录方案数
for(int i=1;i<=bcnt;i++){
int cnt=0,len=bs[i].size();
for(int j=0;j<len;j++)
if(ic[bs[i][j]])
cnt++;
if(!cnt)
if(len>1){
ans1+=2;
ans2*=len*(len-1)/2;
}
else
ans1++;
else if(cnt==1){
ans1++;
ans2*=len-1;
}
}
printf("Case %d: %d %llu\n",++t,ans1,ans2);
}
return 0;
}


（任意一个塌了可以用另外一个）

### 判断一个点是否为割点

if(x!=root&&low[y]>=x)


if(x==root&&cnt>1)


### c++代码实现

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned long long ULL;
const int N=1010;
int to[N],ne[N],h[N],idx;   //邻接表的那几个数组和变量
int low[N],dft[N],nowt; //tarjan算法的数组和变量
int s[N],tt;    //tarjan算法中的栈
int root;   //当前遍历的起始节点
bool ic[N]; //记录该点是否为割点
vector<int> bs[N];  //存每个块的所有点
int bcnt;   //块数
inline void add(int a,int b){   //邻接表加边
to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){ //缩点
dft[x]=low[x]=++nowt;   //打上标记
s[++tt]=x;  //入栈
if(!h[x]){  //孤立的点
bcnt++;
bs[bcnt].push_back(x);
return;
}
int cnt=0;  //记录下面有几个块
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(!dft[y]){    //还没遍历过
tarjan(y);
low[x]=min(low[x],low[y]);
if(dft[x]<=low[y]){
cnt++;
if(x!=root||cnt>1)
ic[x]=1;
++bcnt;
do{ //缩成块
bs[bcnt].push_back(s[tt]);
}while(s[tt--]!=y);
bs[bcnt].push_back(x);  //x也是块内的点，但不出栈
}
}
else    //遍历过了，是上面的节点
low[x]=min(low[x],dft[y]);
}
}
int main(){
int t=0,m;
while(scanf("%d",&m),m){
memset(h,0,sizeof h);
memset(ic,0,sizeof ic);
memset(dft,0,sizeof dft);
for(int i=1;i<=bcnt;i++)
bs[i].clear();  //初始化数组和vector
idx=1;
nowt=bcnt=0;    //初始化变量
int n=0;
while(m--){ //加边
int a,b;
scanf("%d%d",&a,&b);
n=max(n,a);
n=max(n,b); //题目的n要自己算
}
for(root=1;root<=n;root++)  //遍历所有连通块
if(!dft[root])
tarjan(root);
int ans1=0; //记录最少出口数
ULL ans2=1; //记录方案数
for(int i=1;i<=bcnt;i++){
int cnt=0,len=bs[i].size();
for(int j=0;j<len;j++)  //记录该块中有几个割点
if(ic[bs[i][j]])
cnt++;
if(!cnt)    //没有割点
if(len>1){
ans1+=2;
ans2*=len*(len-1)/2;
}
else
ans1++;
else if(cnt==1){    //有一个割点
ans1++;
ans2*=len-1;
}
}
printf("Case %d: %d %llu\n",++t,ans1,ans2); //输出答案
}
return 0;
}


tarjan算法

#include<iostream>
#include<cstring>
using namespace std;
const int N=10010,M=30010;
int to[M],ne[M],h[N],idx;
int low[N],dft[N],nowt;
int root;
int ans,cnt;
to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){
low[x]=dft[x]=++nowt;
int res=0;
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(!dft[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
res+=low[y]>=dft[x];
}
else
low[x]=min(low[x],dft[y]);
}
if(x!=root)
res++;
ans=max(ans,res);
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m),n||m){
idx=1;
nowt=0;
memset(h,0,sizeof h);
memset(dft,0,sizeof dft);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
}
ans=cnt=0;
for(root=0;root<n;root++)
if(!dft[root]){
cnt++;
tarjan(root);
}
printf("%d\n",ans+cnt-1);
}
return 0;
}


#include<iostream>
#include<cstring>
using namespace std;
const int N=210;
int n,m;
int match[N];
bool way[N][N],vis[N];
bool find(int x){
for(int i=1;i<=n;i++)
if(!vis[i]&&way[x][i]){
vis[i]=1;
if(!match[i]||find(match[i])){
match[i]=x;
return 1;
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
way[x][y]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
way[i][j]|=way[i][k]&&way[k][j];
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof vis);
ans+=find(i);
}
printf("%d",n-ans);
return 0;
}


#include<iostream>
#include<unordered_set>
using namespace std;
typedef long long LL;
const int N=100010,M=2000010;
int to[M],ne[M],h[N],h2[N],idx=1;
int dft[N],low[N],nowt;
int s[N],tt;
bool ins[N];
int block[N],bcnt,num[N];
int f[N],cnt[N];
inline void add(int h[],int a,int b){
to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){
dft[x]=low[x]=++nowt;
s[++tt]=x;
ins[x]=1;
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(!dft[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dft[y]);
}
if(low[x]==dft[x]){
++bcnt;
do{
block[s[tt]]=bcnt;
num[bcnt]++;
ins[s[tt]]=0;
}while(s[tt--]!=x);
}
}
int main(){
int n,m,mod;
scanf("%d%d%d",&n,&m,&mod);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
}
for(int i=1;i<=n;i++)
if(!dft[i])
tarjan(i);
unordered_set<LL> he;
for(int i=1;i<=n;i++)
for(int j=h[i];j;j=ne[j]){
int y=to[j];
LL hash=block[i]*1000000ll+block[y];
if(block[i]!=block[y]&&!he.count(hash)){
he.insert(hash);
}
}
for(int i=bcnt;i;i--){
if(!f[i]){
f[i]=num[i];
cnt[i]=1;
}
for(int j=h2[i];j;j=ne[j]){
int y=to[j];
if(f[y]<f[i]+num[y]){
f[y]=f[i]+num[y];
cnt[y]=cnt[i];
}
else if(f[y]==f[i]+num[y])
cnt[y]=(cnt[y]+cnt[i])%mod;
}
}
int ans1=0,ans2=0;
for(int i=1;i<=bcnt;i++)
if(f[i]>ans1){
ans1=f[i];
ans2=cnt[i];
}
else if(f[i]==ans1)
ans2=(ans2+cnt[i])%mod;
printf("%d\n%d",ans1,ans2);
return 0;
}


#include<iostream>
using namespace std;
const int N=5010,M=20010;
int to[M],ne[M],h[N],idx=1;
int dft[N],low[N],nowt;
int block[N],bnum;
int s[N],tt;
int cnt[N];
to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x,int fe){
dft[x]=low[x]=++nowt;
s[++tt]=x;
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(!dft[y]){
dfs(y,i);
low[x]=min(low[x],low[y]);
}
else if(i+1>>1!=fe+1>>1)
low[x]=min(low[x],dft[y]);
}
if(low[x]==dft[x]){
bnum++;
do
block[s[tt]]=bnum;
while(s[tt--]!=x);
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
}
dfs(1,-1);
for(int i=1;i<=n;i++)
for(int j=h[i];j;j=ne[j]){
int y=to[j];
if(block[i]!=block[y])
cnt[block[y]]++;
}
int ans=0;
for(int i=1;i<=bnum;i++)
if(cnt[i]==1)
ans++;
printf("%d",ans+1>>1);
return 0;
}


#include<iostream>
using namespace std;
const int N=100010,M=600010;
typedef long long LL;
int to[M],ne[M],w[M],h[N],idx=1;
int h2[N];
int dft[N],low[N],nowt;
int s[N],tt;
bool ins[N];
int block[N],bnum;
int dist[N],num[N];
inline void add(int h[],int a,int b,int c){
to[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x){
dft[x]=low[x]=++nowt;
ins[x]=1;
s[++tt]=x;
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(!dft[y]){
dfs(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dft[y]);
}
if(low[x]==dft[x]){
++bnum;
do{
ins[s[tt]]=0;
block[s[tt]]=bnum;
num[bnum]++;
}while(s[tt--]!=x);
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
while(m--){
int type,a,b;
scanf("%d%d%d",&type,&a,&b);
if(type==1){
}
else if(type==2)
else if(type==3)
else if(type==4)
else
}
dfs(0);
bool flag=1;
for(int i=0;i<=n;i++){
for(int j=h[i];j;j=ne[j]){
int y=to[j];
if(block[i]==block[y]&&w[j]>0){
flag=0;
break;
}
}
if(!flag)
break;
}
if(!flag)
printf("-1");
else{
for(int i=bnum;i;i--){
for(int j=h2[i];j;j=ne[j]){
int y=to[j];
dist[y]=max(dist[y],dist[i]+w[j]);
}
}
LL ans=0;
for(int i=1;i<=bnum;i++)
ans+=(LL)dist[i]*num[i];
printf("%lld",ans);
}
return 0;
}


#include<iostream>
using namespace std;
const int N=110,M=10010;
int to[M],ne[M],h[N],idx=1;
int s[N],tt;
bool ins[N];
int nowt;
int dft[N],low[N];
int block[N],bcnt;
int in[N],out[N];
inline void add(int a,int b){   //邻接表加边
to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x){    //缩点
s[++tt]=x;
ins[x]=1;
dft[x]=low[x]=++nowt;
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(!dft[y]){
dfs(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dft[y]);
}
if(low[x]==dft[x]){
++bcnt;
do{
block[s[tt]]=bcnt;
ins[s[tt]]=0;
}while(s[tt--]!=x);
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
while(scanf("%d",&x),x)
}
for(int i=1;i<=n;i++)
if(!dft[i])
dfs(i);
for(int i=1;i<=n;i++)
for(int j=h[i];j;j=ne[j]){
int a=block[i],b=block[to[j]];
if(a!=b){
in[b]++;
out[a]++;
}
}
int scnt=0,tcnt=0;
for(int i=1;i<=bcnt;i++){   //记录没有入边的块和没有出边的块
if(!in[i])
scnt++;
if(!out[i])
tcnt++;
}
printf("%d\n",scnt);
if(bcnt==1)
printf("%d",0);
else
printf("%d",max(scnt,tcnt));
return 0;
}


#include<iostream>
using namespace std;
const int N=10010,M=50010;
int to[M],ne[M],h[N],idx=1;
int to2[M],ne2[M],h2[N];
int dft[N],low[N];
bool vis[N];
int nowt;
int s[N],tt;
bool ins[N];
int fa[N],num[N];
bool ho[N];
inline int find(int x){
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
inline void pt(int x,int y){
int a=find(x),b=find(y);
if(a==b)
return;
num[a]+=num[b];
fa[b]=a;
}
to[idx]=b,ne[idx]=h[a],h[a]=idx;
to2[idx]=a,ne2[idx]=h2[b],h2[b]=idx++;
}
void dfs1(int x){
s[++tt]=x,ins[x]=1;
dft[x]=low[x]=++nowt;
for(int i=h[x];i;i=ne[i]){
int y=to[i];
if(!dft[y]){
dfs1(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dft[y]);
}
if(low[x]==dft[x])
do{
ins[s[tt]]=0;
pt(x,s[tt]);
}while(s[tt--]!=x);
}
void dfs2(int x){
vis[x]=1;
for(int i=h2[x];i;i=ne2[i]){
int y=to2[i];
if(!vis[y])
dfs2(y);
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
fa[i]=i;
num[i]=1;
}
while(m--){
int a,b;
scanf("%d%d",&a,&b);
}
for(int i=1;i<=n;i++)
if(!dft[i])
dfs1(i);
for(int i=1;i<idx;i++){
int a=find(to2[i]),b=find(to[i]);
if(a!=b)
ho[a]=1;
}
int ans=0;
for(int i=1;i<=n;i++){
int a=find(i);
if(!ho[a]){
if(ans&&ans!=a){
printf("0");
return 0;
}
ans=a;
}
}
dfs2(ans);
for(int i=1;i<=n;i++)
if(!vis[i]){
printf("0");
return 0;
}
printf("%d",num[ans]);
return 0;
}