`
Coco_young
  • 浏览: 125521 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

SCC_Gabow

 
阅读更多
#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 1001;
vector<int> g[MAXN];//adjlist
stack<int> S,P;
int belong[MAXN],vis[MAXN],indeg[MAXN],sccg[MAXN][MAXN],scccnt,disc[MAXN];
void init()
{
	for(int i=0;i<MAXN;i++)g[i].clear();
	memset(belong,-1,sizeof(belong));
	memset(vis,0,sizeof(vis));
	scccnt = 0;
	memset(sccg,0,sizeof(sccg));
	memset(indeg,0,sizeof(indeg));
	while(!S.empty())S.pop();
	while(!P.empty())P.pop();
}
void dfs_scc(int u,int &time)
{
	disc[u] = time++;
	S.push(u);
	P.push(u);
	vis[u] = 1;
	for(int i=0;i<g[u].size();i++)
	{
		int v = g[u][i];
		if(!vis[v])
		{
			dfs_scc(v,time);
		}
		else if(belong[v]==-1)
		{
			while(disc[P.top()]>disc[v])P.pop();
		}
	}
	if(P.top()==u)
	{
		while(S.top()!=u)
		{
			int v = S.top();
			belong[v] = scccnt;
			S.pop();
		}
		S.pop();
		belong[u] = scccnt;
		P.pop();
		scccnt++;
	}
}
void Gabow(int n)
{
	int time = 0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])dfs_scc(i,time);
	}
}
void make_sccg(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<g[i].size();j++)
		{
			if(belong[i]!=belong[g[i][j]])
			{
				sccg[belong[i]][belong[g[i][j]]]=1;
			}
		}
	}
}
void cac_indeg()
{
	for(int i=0;i<scccnt;i++)
	{
		for(int j=0;j<scccnt;j++)
		{
			if(sccg[j][i])indeg[i]++;
		}
	}
}
bool solve(int n)
{
	Gabow(n);
	make_sccg(n);
	cac_indeg();
	memset(vis,0,sizeof(vis));
	for(int i=0;i<scccnt;i++)
	{
		int cnt=0,v;
		for(int j=0;j<scccnt;j++)
		{
			if(indeg[j]==0&&!vis[j])v=j,cnt++;
		}
		if(cnt!=1)return false;
		vis[v] = 1;
		for(int w=0;w<scccnt;w++)
		{
			if(sccg[v][w])indeg[w]--;
		}
	}
	return true;
}
int main()
{
	int t,n,m;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		init();
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			g[a].push_back(b);
		}
		bool ok = solve(n);
		if(ok) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

分享到:
评论

相关推荐

    SCC.rar_SCC_matlabSCC算法_scc 分类_scc的工作原理_图像分类

    SCC(Self-Consistent Clustering,自洽聚类)是一种在图像分类领域广泛应用的算法。它基于数据的内在结构和相似性,通过迭代过程来不断优化聚类结果,达到自洽状态,即聚类结果与原始数据的相似度矩阵一致。在...

    SCC.rar_SCC_VC 串口

    标题中的"SCC.rar_SCC_VC 串口"指的是一个使用VC++开发的串口通信监控软件,名为SCC(可能代表Serial Communication Controller)。这个软件主要用于通过串行接口与外部设备进行数据交换,并且其用户界面设计采用了...

    欧姆龙安全产品sge_scc_ca_c_8_2.pdf

    《欧姆龙安全产品Sge_Scc_Ca_C_8_2.pdf》是欧姆龙公司推出的关于其安全产品系列的详细说明书。该文档主要涵盖了欧姆龙的SGE和SCC系列的安全传感器,这些产品在工业自动化领域广泛应用,旨在确保工作场所的安全,预防...

    SCC_SerialVC++_Vc_strengthim4_

    标题"SCC_SerialVC++_Vc_strengthim4_"暗示了这是一个关于使用VC++实现串口控制的应用,而“strengthim4”可能是指程序的特定功能或版本号。 串口通信的基础知识是理解COM端口,它是计算机与外部设备通信的接口。在...

    modRankineSCC-master_rankine_matlab_SCC_

    本项目"modRankineSCC-master_rankine_matlab_SCC_"是通过MATLAB编程实现的,目的是计算变工况下兰金循环的性能参数,特别是采用SCC(Supercritical Carbon Dioxide,超临界二氧化碳)作为工质的情况。 超临界二...

    scc.rar_CAD 间距图元_SCC_cad 归正坐标_cad 轴线_多段线

    对CAD的图元或者图元的相对距离零碎数归整,如端点、顶点、线段的 ;;;长度的零碎数归整,轴线之间距取整等等。 ;;;适用于斯维尔,天正,直线,圆,弧,多段线,块。...譬如歪斜不平的线段可以摆平,轴线间距归整,Z...

    SCC_人脸识别_聚类_稀疏_稀疏聚类_稀疏表示_

    在这个场景中,我们关注的是“基于稀疏表示的聚类算法”(Sparse Representation-based Clustering, 简称SCC),这是一种融合了稀疏表示理论和聚类算法的创新技术。 稀疏表示的概念源于信号处理和机器学习,其核心...

    CVS_SCC_proxy_v1.2.rar

    让VC的IDE也能随意的使用CVS的插件

    欧姆龙安全产品sge_scc_f088-e1_8_2_csm2126.pdf

    欧姆龙公司提供的这份产品样本介绍了一款名为SGE/SCC的新安全边产品系列,该产品主要应用于机械设备的安全保护。SGE(SafetyEdge)安全边是一种安装于机械设备移动部件如门和围栏上的安全传感器,当检测到与人员或...

    sparse-subspace-clustering-admm-master_SCC_admm_

    SCC的关键函数主要包括两个部分:稀疏编码和子空间一致性。稀疏编码阶段,每个数据点被表示为其他数据点的线性组合,且这种组合尽可能地稀疏,即大多数系数为零。这可以通过优化问题来实现,例如最小化L1范数(鼓励...

    IBM_SCC_Boston_Report_Final_LR_tcm3-36399.pdf

    报告概述了IBM在2012年为波士顿市提供的Smarter Cities Challenge项目,作为IBM建设更智能地球公民计划的一部分。该项目旨在通过解锁、分享和分析交通数据,帮助波士顿实现气候和交通改善目标。...

    安全中心整站系统(SCC_WebSystem) v1.20

    安全中心整站系统是一个网络安全类整站系统。由七个模块组成,其中包括:文章系统(安全文档)、下载系统(安全工具、**作品)、漏洞发布系统(安全漏洞)、代码发布模块(漏洞利用)、在线申请模块(工作室)和信息...

    scc.rar_connected component_scc java_强连通_有向图

    "connected component"和"scc_java"标签表明这个程序或数据集关注的是寻找有向图的强连通分量。"强连通"指的是图中的一种特定结构,"有向图"则明确了图的类型。 描述中提到的算法是递归地求解有向图的强连通分量。...

    安全中心整站系统(SCC_WebSystem) v1.20 -ASP源码.zip

    ASP源码,压缩包解压密码:www.cqlsoft.com

    SCC_Project:羊和狼,meeeeeee

    【标题】"SCC_Project:羊和狼,meeeeeee" 暗示这是一个与游戏或模拟相关的项目,其中可能包含“羊”和“狼”这两个元素的角色或逻辑。"SCC"通常代表Strongly Connected Components,这在图论中是一个重要的概念,...

    CS131_02_SCC_Polymorphism活动

    【标题】"CS131_02_SCC_Polymorphism活动" 指的是一场关于计算机科学课程CS131中的第二部分,主题是"结构化并发与控制(Structured Concurrency and Control)",重点探讨的是多态性(Polymorphism)在编程中的应用...

    parallel_union_find:C ++库,用于基于纸张并行查找强连接的组件

    仅标头的库,用于并行查找强连接的组件用法示例: # include &lt; vector&gt;# include &lt; thread&gt;# include &lt; cassert&gt;# include " parallel_union_find/algorithm/multi_core_on_the_fly_scc_decomposition_algorithm.hpp...

    FTP.rar_SCC FTP_VB FTP下载

    FTP(File Transfer Protocol)是一种广泛使用的网络协议,用于在互联网上进行文件的上传和下载。在VB(Visual Basic)环境中,开发FTP客户端程序可以方便地实现这一功能。VB FTP客户端通常涉及以下关键知识点: ...

    SCC.rar_C编译器_SCC

    【标题】"SCC.rar_C编译器_SCC"指的是一个名为SCC的C语言编译器项目,它被封装在一个RAR压缩包中。SCC是Simple C Compiler的缩写,意味着这是一个为了理解和学习编译原理而设计的简单C语言编译器。这个项目可能包含...

    scc.rar_SCC

    《SCC:深入理解编译器词法分析器》 在计算机科学领域,编译器是将高级语言转化为机器语言的重要工具,而词法分析器则是编译器的第一道工序,它负责识别源代码中的词汇元素,为后续的语法分析和语义分析打下基础。...

Global site tag (gtag.js) - Google Analytics