Homework Introduction

#include <bits/stdc++.h>
using namespace std;
const int N = 3e4+5;
struct node{
	int nxt,to;
}e[N*2];
int n,m,head[N],cnt=-1;
int dfn[N],low[N],tot,res;
void add(int x,int y){
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void tarjan(int x,int lst){
	dfn[x] = low[x] = ++tot;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int v = e[i].to;
		if(i==(lst^1))continue;
		if(!dfn[v]){
			tarjan(v,i);
			low[x] = min(low[x],low[v]);
			if(low[v]>dfn[x])res++;
		}
		else{
			low[x] = min(low[x],dfn[v]);
		}
	}
}
int main(){
	while(cin>>n>>m){
		if(n+m==0)break;
		for(int i=1;i<=n;i++){
			head[i] = -1;
			dfn[i] = low[i] = 0;
		}
		res = 0;cnt = -1;tot=0;
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			add(x,y);
			add(y,x);
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i]){
				tarjan(i,-1);
			}
		}
		cout<<res<<endl;
	}
	return 0;
}
}

/*
low[v]>=dfn[x] 割点
if(x==root && son[x]>=2)割点
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4+5,M=1e5+5;
struct node{
	int nxt,to;
}e[M<<1];
int n,m,head[N],cnt=-1;
int dfn[N],low[N],tot,cut[N],res;
void add(int x,int y){
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void tarjan(int x,int lst,int root){
	dfn[x] = low[x] = ++tot;
	int son = 0;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int v = e[i].to;
		if(i==(lst^1))continue;
		if(!dfn[v]){
			son++;
			tarjan(v,i,root);
			low[x] = min(low[x],low[v]);
			if(x!=root && low[v]>=dfn[x])cut[x] = 1;
			if(x==root && son>=2)cut[x] = 1;
		}
		else low[x] = min(low[x],dfn[v]);
	}
}
int main(){
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	cnt = -1;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i,-1,i);
	}
	for(int i=1;i<=n;i++){
		if(cut[i])res++;
	}
	cout<<res<<endl;
	for(int i=1;i<=n;i++){
		if(cut[i]==1)cout<<i<<" ";
	}
	return 0;
}

/*
low[v]>=dfn[x] 割点
if(x==root && son[x]>=2)割点
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4+5,M=1e5+5;
struct node{
	int nxt,to;
}e[M<<1];
int n,m,head[N],cnt=-1;
int dfn[N],low[N],tot,cut[N],res;
void add(int x,int y){
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void tarjan(int x,int lst,int root){
	dfn[x] = low[x] = ++tot;
	int son = 0;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int v = e[i].to;
		if(i==(lst^1))continue;
		if(!dfn[v]){
			son++;
			tarjan(v,i,root);
			low[x] = min(low[x],low[v]);
			if(x!=root && low[v]>=dfn[x])cut[x] = 1;
			if(x==root && son>=2)cut[x] = 1;
		}
		else low[x] = min(low[x],dfn[v]);
	}
}
int main(){
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	cnt = -1;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i,-1,i);
	}
	for(int i=1;i<=n;i++){
		if(cut[i])res++;
	}
	cout<<res<<endl;
	for(int i=1;i<=n;i++){
		if(cut[i]==1)cout<<i<<" ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5,M=2e6+5;
struct node{
	int nxt,to;
}e[M<<1];
int n,m,head[N],cnt=-1;
int dfn[N],low[N],tot,num;
stack<int>stk;
vector<int>edcc[N];
void add(int x,int y){
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void tarjan(int x,int lst){
	low[x] = dfn[x] = ++tot;
	stk.push(x);
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int v = e[i].to;
		if(i==(lst^1))continue;
		if(!dfn[v]){
			tarjan(v,i);
			low[x] = min(low[x],low[v]);
		}
		else{
			low[x] = min(low[x],dfn[v]);
		}
	}
	if(low[x]==dfn[x]){
		num++;
		int v;
		do{
			v = stk.top();stk.pop();
			edcc[num].push_back(v);
		}while(v!=x);
	}
}
int main(){
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i,-1);
	}
	cout<<num<<endl;
	for(int i=1;i<=num;i++){
		cout<<edcc[i].size()<<" ";
		for(auto v:edcc[i])cout<<v<<" ";
		cout<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5,M=2e6+5;
struct node{
	int nxt,to;
}e[M<<1];
int n,m,head[N],cnt=-1;
int dfn[N],low[N],tot,num,cut[N];
stack<int>stk;
vector<int>vdcc[N];
void add(int x,int y){
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void tarjan(int x,int lst,int root){
	low[x] = dfn[x] = ++tot;
	if(head[x]==-1 && x==root){
		num++;
		vdcc[num].push_back(x);
		return;
	}
	stk.push(x);
	int son = 0;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int v = e[i].to;
		if(i==(lst^1))continue;
		if(!dfn[v]){
			son++;
			tarjan(v,i,root);
			low[x] = min(low[x],low[v]);
			if(low[v]>=dfn[x]){
				if(x!=root || son>1)cut[x] = 1;
				int V;
				num++;
				do{
					V = stk.top();
					stk.pop();
					vdcc[num].push_back(V);
				}while(V!=v);
				vdcc[num].push_back(x);
			}
		}
		else{
			low[x] = min(low[x],dfn[v]);
		}
	}
}
int main(){
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x==y)continue;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i,-1,i);
	}
	cout<<num<<endl;
	for(int i=1;i<=num;i++){
		cout<<vdcc[i].size()<<" ";
		for(auto v:vdcc[i])cout<<v<<" ";
		cout<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5,M=1e6+5;
struct node{
	int nxt,to;
}e[M<<1];
int n,m,head[N],cnt=-1;
int dfn[N],low[N],vis[N],tot,res,book[N],d;
int f[N];
//f[x]以x为起点，最长的路径的长度
/*
d 直径
d = max(f[x]+f[v]+1)
f[x] = max(f[x],f[v]+1)
*/
void add(int x,int y){
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void tarjan(int x,int lst){
	dfn[x] = low[x] = ++tot;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int v = e[i].to;
		if(i==(lst^1))continue;
		if(!dfn[v]){
			tarjan(v,i);
			low[x] = min(low[x],low[v]);
			if(low[v]>dfn[x]){
				//说明第i条边是桥
				vis[i] = vis[i^1] = 1;
				res++;
			}
		}
		else low[x] = min(low[x],dfn[v]);
	}
}
void dfs(int x,int fa)
{
	book[x] = 1;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int v = e[i].to;
		if(v==fa || book[v]==1)continue;
		dfs(v,x);
		d = max(f[x]+f[v]+vis[i],d);
		f[x] = max(f[x],f[v]+vis[i]);
	}
}
int main(){
	while(cin>>n>>m){
		for(int i=1;i<=n;i++){
			head[i] = -1;
			low[i] = dfn[i] = vis[i] = f[i] = book[i] = 0;
		}
		res = 0,tot=0,cnt=-1;
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			add(x,y);
			add(y,x);
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i])tarjan(i,-1);
		}
		dfs(1,0);
		cout<<res-d<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
char mat[N][N];
int n,m,sx,sy,boxx,boxy,fx,fy;
struct node{
	int nxt,to;
}e[N*N*N*10];
int nxt[4][2]={0,1,0,-1,1,0,-1,0};
int tot,low[N*N],dfn[N*N],cut[N*N];
int head[N*N],cnt=-1,num,rt[N*N];
struct point{
	int x,y,dir,cost;
	friend bool operator < (point a,point b){
		return a.cost>b.cost;
	}
};
int f[N][N][4],book[N][N];
vector<int>dcc[N*N];
stack<int>stk;
vector<int>id[N*N];
map<pair<int,int>,int>mp;
int Get(int x,int y){
	return (x-1)*m+y;
}
void add(int x,int y){
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
void tarjan(int x,int lst,int root){
	rt[x] = root;
	dfn[x] = low[x] =++tot;
	stk.push(x);
	int son = 0;
	for(int i=head[x];i!=-1;i=e[i].nxt){
		int v = e[i].to;
		if(i==(lst^1))continue;
		if(!dfn[v]){
			son++;
			tarjan(v,i,root);
			low[x] = min(low[x],low[v]);
			if(low[v]>=dfn[x]){
				if(son>1 || x!=root)cut[x] = 1;
				int V;
				num++;
				do{
					V = stk.top();stk.pop();
					dcc[num].push_back(V);
					id[V].push_back(num);
				}while(V!=v);
				dcc[num].push_back(x);
				id[x].push_back(num);
			}
		}
		else low[x] = min(low[x],dfn[v]);
	}
}
int check(int x,int y){
	for(int j=0;j<id[y].size();j++){
		int idy=id[y][j];
		if(find(dcc[idy].begin(),dcc[idy].end(),x)!=dcc[idy].end())return 1;
	}
	return 0;
}
void bfs(){
	memset(f,0x3f,sizeof(f));
	queue<point>pq;
	pq.push({sx,sy,0,0});
	book[sx][sy] = 1;
	while(!pq.empty()){
		point tmp = pq.front();
		pq.pop();
		for(int i=0;i<4;i++){
			int nx = tmp.x+nxt[i][0];
			int ny = tmp.y+nxt[i][1];
			if(nx>=1 && nx<=n && ny>=1 && ny<=m){
				if(mat[nx][ny]!='S' && mat[nx][ny]!='P' && book[nx][ny]==0){
					book[nx][ny] = 1;
					pq.push(point{nx,ny,0,0});
				}
			}
		}
	}
	priority_queue<point>q;
	for(int i=0;i<4;i++){
		int nx = boxx+nxt[i][0];
		int ny = boxy+nxt[i][1];
		if(nx>=1 && nx<=n && ny>=1 && ny<=m && mat[nx][ny]!='S' && book[nx][ny]==1){
			f[boxx][boxy][i] = 0;
			q.push(point{boxx,boxy,i,0});
		}
	}
	while(!q.empty()){
		point tmp = q.top();
		q.pop();
		for(int i=0;i<4;i++){
			int nx = tmp.x+nxt[i][0];
			int ny = tmp.y+nxt[i][1];
			int px = tmp.x-nxt[i][0];
			int py = tmp.y-nxt[i][1];
			int oldx = tmp.x+nxt[tmp.dir][0];
			int oldy = tmp.y+nxt[tmp.dir][1];
			if(px<1 || px>n || py<1 || py>m || oldx<1 || oldx>n || oldy<1 || oldy>m)continue;
			if(nx>=1 && nx<=n && ny>=1 && ny<=m){
				if(mat[nx][ny]!='S' && mat[px][py]!='S' && mat[oldx][oldy]!='S'){
					//1.箱子不在割点上 只要两个同根就可以走
					if(rt[Get(px,py)]==rt[Get(oldx,oldy)]){
						if(cut[Get(tmp.x,tmp.y)]==0){
							if(tmp.cost+1<f[nx][ny][i^1]){
							//	cout<<tmp.x<<" "<<tmp.y<<" --->  "<<nx<<" "<<ny<<endl;
								f[nx][ny][i^1] = tmp.cost+1;
								q.push(point{nx,ny,i^1,tmp.cost+1});
							}
						}
						else if(cut[Get(tmp.x,tmp.y)]==1 && check(Get(px,py),Get(oldx,oldy))==1 && tmp.cost+1<f[nx][ny][i^1]){
							f[nx][ny][i^1] = tmp.cost+1;
						//	cout<<tmp.x<<" "<<tmp.y<<"->"<<nx<<" "<<ny<<endl;
							q.push(point{nx,ny,i^1,tmp.cost+1});
						}
					}
				}
			}
		}
	}
	int res = 1e9;
	for(int i=0;i<4;i++){
		int nx = fx+nxt[i][0];
		int ny = fy+nxt[i][1];
		if(nx>=1 && nx<=n && ny>=1 && ny<=m && mat[nx][ny]!='S'){
			res = min(res,f[fx][fy][i]);
		}
	}
	if(res==1e9)cout<<"NO"<<endl;
	else cout<<res<<endl;
}
int main(){
//	freopen("1.out","w",stdout);
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mat[i][j];
			if(mat[i][j]=='M')sx=i,sy=j;
			if(mat[i][j]=='P')boxx=i,boxy=j;
			if(mat[i][j]=='K')fx=i,fy=j;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mat[i][j]=='S')continue;
			for(int k=0;k<4;k++){
				int nx = i+nxt[k][0];
				int ny = j+nxt[k][1];
				if(nx>=1 && nx<=n && ny>=1 && ny<=m){
					if(mat[nx][ny]!='S' && mp[make_pair(Get(i,j),Get(nx,ny))]==0){
						add(Get(i,j),Get(nx,ny));
						add(Get(nx,ny),Get(i,j));
						mp[make_pair(Get(i,j),Get(nx,ny))] = 1;
						mp[make_pair(Get(nx,ny),Get(i,j))] = 1;
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mat[i][j]!='S' && !dfn[Get(i,j)]){
				tarjan(Get(i,j),-1,Get(i,j));
			}
		}
	}
	bfs();
	return 0;
}

Problem

Problem
18227   割边(桥)
P3388   【模板】割点（割顶）
P8435   【模板】点双连通分量
P8436   【模板】边双连通分量
18228   赤壁之战
18229   热身运动
18230   网络
18231   删除两个点
18232   一次就好
18233   仓库管理员
P3225   [HNOI2012] 矿场搭建
P5058   [ZJOI2004] 嗅探器
P7924   「EVOI-RD2」旅行家
P10953   逃不掉的路
P8867   [NOIP2022] 建造军营
P2783   有机化学之神偶尔会做作弊
P3469   [POI 2008] BLO-Blockade
P2542   [AHOI2005] 航线规划
Status
Done
Problem
18
Open Since
2026-1-26 0:00
Deadline
2026-3-31 23:59
Extension
24 hour(s)
  1. Judging Queue
  2. Service Status
  3. Legacy mode
  4. Theme
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 16ms
  4. Powered by Hydro v5.0.0-beta.15 Community