求助(P8436)
  • 板块学术版
  • 楼主emo_zkt
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/13 19:57
  • 上次更新2024/11/13 21:57:57
查看原帖
求助(P8436)
482163
emo_zkt楼主2024/11/13 19:57

最后两个点T了,orz,orz

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
vector<int> ans[N];
int n,m,dfn[N],low[N],sz,num,ind[N],st[N],H[N],f[N],w[N],c[N],d[N],a[N],col[N],vis[N],tot=-1,tp,head[N],cut[N],cnt;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
    while(isdigit(c)){
		x=x*10+c-48;
		c=getchar();
	}
    return x*f;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct nod{
	int u,v,ne;
}e[2*N];
void add(int x,int y){
	e[++tot].u=x;
	e[tot].v=y;
	e[tot].ne=head[x];
	head[x]=tot;
}
void dfs(int u,int fa){
	dfn[u]=low[u]=++cnt,st[++tp]=u,vis[u]=1;
	for(int i=head[u];i!=-1;i=e[i].ne){
		int v=e[i].v;
		if(dfn[v]==0){
			dfs(v,i);
			low[u]=min(low[v],low[u]);
		}
		else if(i!=(fa^1))low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		ans[++num].push_back(u),vis[u]=0;
		int x=1;
		while(st[tp]!=u&&tp!=0){
			int v=st[tp--];
			ans[num].push_back(v);
			vis[v]=0;
			x++;
		}
		tp--;
		c[num]=x;
	}
}
int main(){
	memset(head,-1,sizeof head);
	n=read(),m=read();
	tot=1;
	for(int i=1;i<=m;i++){
		int a,b;
		a=read(),b=read();
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++){
		tp=0;
		if(!dfn[i])dfs(i,0);
	}
	write(num);
	putchar('\n');
	for(int i=1;i<=num;i++){
		write(c[i]);
		putchar(' ');
		for(int j=0;j<ans[i].size();j++)write(ans[i][j]),putchar(' ');
		putchar('\n');
	}
}
2024/11/13 19:57
加载中...