loj 1168(Tarjan应用)

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26882

思路:一开始把题意理解错了,还以为是简单路径,然后仔细一看发现是一条路径,意思就是说从起点出发,把所有的点走一遍,于是就要考虑强连通分量,因为对于同一个强连通分量的点是相互可达的,于是我们可以先缩点,建新图,统计新图中顶点的入度与出度的关系,判断即可。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<list>
using namespace std;
#define MAXN 1111
#define inf 1<<30
#define INF 1LL<<60
#define FILL(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef unsigned long long llu;
typedef pair<int,int>PP;
template<class T> inline T Get_MIN(const T &a,const T &b){ return a < b ? a : b; }
template<class T> inline T Get_MAX(const T &a,const T &b){ return a > b ? a : b; }
template<class T> inline T ABS(const T &a){ return a < ? -a : a; } int n,m,k;
bool vis[MAXN];
vector<vector<int> >g,num;
map<int,int>ID; int low[MAXN],dfn[MAXN],color[MAXN];
int scc_count,cnt;
bool mark[MAXN];
stack<int>S; void Tarjan(int u)
{
low[u]=dfn[u]=++cnt;
mark[u]=true;
S.push(u);
for(int i=;i<g[u].size();i++){
int v=g[u][i];
if(dfn[v]==){
Tarjan(v);
low[u]=Get_MIN(low[u],low[v]);
}else if(mark[v]){
low[u]=Get_MIN(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
scc_count++;
int v;
do{
v=S.top();
S.pop();
mark[v]=false;
color[v]=scc_count;
}while(u!=v);
}
} int In_degree[MAXN],Out_degree[MAXN];
void Build()
{
FILL(In_degree,);
FILL(Out_degree,);
for(int u=;u<=m;u++){
for(int i=;i<g[u].size();i++){
int v=g[u][i];
if(color[u]!=color[v]){
In_degree[color[v]]++;
Out_degree[color[u]]++;
}
}
}
} int main()
{
int _case,u,v,t=;
scanf("%d",&_case);
while(_case--){
scanf("%d",&n);
g.clear();
g.resize();
num.clear();
num.resize();
ID.clear();
FILL(vis,false);
m=;
for(int i=;i<=n;i++){
scanf("%d",&k);
while(k--){
scanf("%d%d",&u,&v);
if(!vis[u])vis[u]=true,ID[u]=++m;
if(!vis[v])vis[v]=true,ID[v]=++m;
g[ID[u]].push_back(ID[v]);
}
}
FILL(dfn,);
FILL(mark,false);
scc_count=cnt=;
for(int i=;i<=m;i++){
if(dfn[i]==)Tarjan(i);
}
printf("Case %d: ",t++);
if(scc_count==){
puts("YES");
continue;
}
Build();
if(Out_degree[color[ID[]]]==||In_degree[color[ID[]]]!=){
puts("NO");
continue;
}
int cnt1,cnt2,cnt3;
cnt1=cnt2=cnt3=;
for(int i=;i<=scc_count;i++){
if(In_degree[i]==&&Out_degree[i]==)cnt1++;
else if(In_degree[i]==&&Out_degree[i]==)cnt2++;
else if(In_degree[i]==&&Out_degree[i]==)cnt3++;
}
if(cnt1==&&cnt2==&&cnt1+cnt2+cnt3==scc_count){
puts("YES");
}else
puts("NO");
}
return ;
}
上一篇:EF如何操作内存中的数据和加载外键数据:延迟加载、贪婪加载、显示加载


下一篇:[转]"git rm" 和 "rm" 的区别