POJ 2117 Electricity (无向图求割点)

今天药忘吃喽~ 2022-08-10 14:45 142阅读 0赞

题目：对于给出的无向图，删除某个顶点后，会得到多个连通分量。求最多的连通分量数（删除某点后）。

每组数据的第一行两个数N和M，表示顶点和边。顶点编号0到N-1。接下来M行，每行一条边。输入以N=M=0结束。每组数据输出一行。1 <= N <= 10 000，M<=1000000。

思路：由于图不一定连通，所以枚举图中每一个连通分量，统计出原图共几个连通分量，再通过求图割点时统计出每个割点能分出多少个连通分量，并统计出最多的数量，再和原图连通分量相加即为答案。

#include <cstdio>
    #include <cstring>
    #include <stack>
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    using namespace std;
    
    const int INF=0x3f3f3f3f;
    
    const int nPoint=10010;
    const int nEdges=300005;
    const int nNewmap=1005;  //新图最大节点数
    
    class SCC // strongly connected components
    {//节点标号从1开始
    private:
    	struct Edge
    	{
    		int v,next;
    	}edges[nEdges];
    
    	int dfn[nPoint],low[nPoint],head[nPoint];//dfn(u)为节点u搜索的次序编号(时间戳),low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
    	bool visit[nPoint];   //标记是否在栈中
    	int in[nPoint],out[nPoint],color[nPoint];   //color[]保存各强连通分量包含的节点数,in[]各强连通分量的入度,out[]各强连通分量的出度
    	int belong[nPoint];             //每个结点所对应的强连通分量标号数组
    	bool DAG[nNewmap][nNewmap];      //存储缩点之后的新图,有向无环图DAG
    	int n,e,id,colornum;         //colornum强连通分量的个数
    	int nIn_0,nOut_0;        //nIn_0=0入度为0的点的个数,nOut_0=0出度为0的点个数
    	stack<int> S;
    
    	int cnt[nPoint];   //存储割点被切掉后会新分出的块数,可用来统计割点个数(不为0即为割点)
    
    	void DFS (int u)
    	{
    		int i,top,v;
    		dfn[u]=low[u]=++id;  //id为时间戳
    		S.push(u);
    		visit[u]=true;
    		for (i=head[u];i!=-1;i=edges[i].next)
    		{
    			v=edges[i].v;
    			if (dfn[v]==0)
    			{//未被访问
    				DFS(v);//继续向下找
    				if (low[v]>=dfn[u])  //是割点,统计
    					cnt[u]++;
    				low[u]=min(low[u],low[v]);//更新u节点所能到达的最小层数
    			}
    			else if (visit[v])
    				low[u]=min(low[u],dfn[v]);
    		}
    		if (dfn[u]<=low[u])   //  ==
    		{//如果节点u是强连通分量的根
    			colornum++;   //连通分量标号+1
    			do
    			{
    				top=S.top(); //
    				S.pop();
    				visit[top]=false;
    				belong[top]=colornum; //出栈节点top属于colornum标号的强连通分量
    				color[colornum]++;
    			}while (top!=u);  //直接将u从栈中退出
    		}
    	}
    
    public:
    
    	void Init (int _n)
    	{
    		n=_n;
    		id=colornum=e=0;
    		nIn_0=nOut_0=0;
    		memset(head,-1,sizeof(head));
    		memset(visit,false,sizeof(visit));
    		memset(dfn,0,sizeof(dfn));
    		memset(in,0,sizeof(in));
    		memset(out,0,sizeof(out));
    		memset(cnt,0,sizeof(cnt));
    	}
    
    	void Add (int u,int v)
    	{
    		edges[e].v=v;
    		edges[e].next=head[u];
    		head[u]=e++;
    	}
    
    	int Tarjan ()  //返回强连通分量的个数
    	{
    		while (!S.empty())   //清空栈
    			S.pop();
    		
    		for (int i=1;i<=n;i++)  //枚举每个节点,搜索连通分量
    			if (!dfn[i])   //未被访问
    			{
    				DFS(i);   //则找该节点的连通分量
    				cnt[i]--;   //原来本身有一块
    			}
    		return colornum;
    	}
    
    	void Cal ()    //计算in[],out[],nOut_0,nIn_0
    	{//与TopoOrder ()同时调则无法正确计算 in 数组(重复使用)
    		int i,j;
    		Tarjan();
    		for (i=1;i<=n;i++)
    			for (j=head[i];j!=-1;j=edges[j].next)
    				if (belong[i]!=belong[edges[j].v])
    				{
    					in[belong[edges[j].v]]++;
    					out[belong[i]]++;
    				}
    		for (i=1;i<=colornum;i++)
    		{
    			nOut_0+=!out[i];
    			nIn_0+=!in[i];
    		}
    	}
    
    	void Build ()       //建立新图DAG
    	{
    		memset(DAG,0,sizeof(DAG));
    		for (int i=1;i<=n;i++)
    			for (int j=head[i];j!=-1;j=edges[j].next)
    				if (belong[i]!=belong[edges[j].v])
    					DAG[belong[i]] [belong[edges[j].v]] =true;
    	}
    
    	bool TopoOrder ()  //拓扑排序,返回是否有分叉
    	{//既是否为一条链
    		int i,j;
    		for (i=1;i<=colornum;i++)
    			for (j=1;j<=colornum;j++)
    				if (DAG[i][j]) in[j]++;
    		for (i=1;i<colornum;i++)
    		{
    			int cnt=0;  //分支条数
    			int p=0;  //下一节点
    			for (j=1;j<=colornum && cnt<=1;j++)
    				if (in[j]==0)
    					cnt++,p=j;
    			if (cnt>1) return false;
    			for (j=1;j<=colornum;j++)
    				if (DAG[p][j]) in[j]--;
    			in[p]=INF;
    		}
    		return true;
    	}
    
    	void Deal ()
    	{
    		int j=Tarjan ();
    		int k=0;
    		for (int i=1;i<=n;i++)
    			k=max(k,cnt[i]);
    		printf("%d\n",j+k);
    	}
    }ob;
    
    int main ()
    {
    	int T,n,m;
    	while (~scanf("%d%d",&n,&m),n||m)
    	{
    		int a,b;
    		T=m;
    		ob.Init (n);
    		while (T--)
    		{
    			scanf("%d%d",&a,&b);
    			a++,b++;
    			ob.Add(a,b);
    			ob.Add(b,a);
    		}
    		if (m==0)
    		{
    			printf("%d\n",n-1);
    			continue;
    		}
    		ob.Deal ();
    	}
    	return 0;
    }