#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;
}
分享到:
相关推荐
IBM_SCC_Boston_Report_Final_LR_tcm3-36399.pdf
欧姆龙安全产品sge_scc_ca_c_8_2pdf,
基于流行分类原理,对图形和图像进行分类处理,采用SCC算法
欧姆龙安全产品sge_scc_f088-e1_8_2_csm2126pdf,
对CAD的图元或者图元的相对距离零碎数归整,如端点、顶点、线段的 ;;;长度的零碎数归整,轴线之间距取整等等。 ;;;适用于斯维尔,天正,直线,圆,弧,多段线,块。...譬如歪斜不平的线段可以摆平,轴线间距归整,Z...
VC++写的串口通讯监视软件,尤其是它的界面也是值得学习的,类似OFFICE的风格。
基于稀疏表示的聚类算法(SCC)
matlab编程实现用SCC方法计算变工况兰肯循环下的负荷参数。
VC++基于串口的监视程序,通过串口发消息的形式,来监视串口的各相操作,在发送方式,可选择循环发送、触发式发送,还可设置两者混合发送。
SCC的关键函数
让VC的IDE也能随意的使用CVS的插件
安全中心整站系统是一个网络安全类整站系统。由七个模块组成,其中包括:文章系统(安全文档)、下载系统(安全工具、**作品)、漏洞发布系统(安全漏洞)、代码发布模块(漏洞利用)、在线申请模块(工作室)和信息...
ASP源码,压缩包解压密码:www.cqlsoft.com
CS131_02_SCC_Polymorphism活动
SCC_项目羊和狼,meeeeeee
递归算法求一个有向图的强连通分量,输入格式如压缩包中data4.txt,第一行为顶点个数。输出到result.txt中。
仅标头的库,用于并行查找强连接的组件用法示例: # include < vector># include < thread># include < cassert># include " parallel_union_find/algorithm/multi_core_on_the_fly_scc_decomposition_algorithm.hpp...
VB FTP客户端,输入IP,账户与密码连接后,可以从本地上传文件至服务器,也可以从服务器下载文件到本地。
这是一个 vb2005+access 数据库实例程序 程序只有一个窗体,讲解了具体的数据库连接、插入、查询基本操作,是入门学习数据库连接、插入、查询的好程序。 程序运行方法,我加上去了。欢迎下载。
本代码应用于串口通信的应用熟悉Tornado的集成开发环境,通过CS850(CPU是Motorola的Power PC 850)的SCC(Serial Communication Controller)端口在NMSI方式下实现HDLC(High Data Link Communication)协议的自环...