i57500网站开发,做网站的多钱,郑州网站优化培训机构,赤峰市网站建设link
题意#xff1a; 首先看到排名自然想到拓扑序#xff0c;但是存在等于的情况#xff0c;这就启发我们把等于的情况缩成一个点#xff0c;让后在缩点后的图中进行拓扑即可。 对于不合法的情况当然是拓扑序没有遍历到应该遍历的点#xff0c;所以只需要检查遍历了几个…link
题意 首先看到排名自然想到拓扑序但是存在等于的情况这就启发我们把等于的情况缩成一个点让后在缩点后的图中进行拓扑即可。 对于不合法的情况当然是拓扑序没有遍历到应该遍历的点所以只需要检查遍历了几个点即可。对于信息不全的情况那就是对应同一级存在多个点所以只需要判断队列是否恒为一个元素即可(当然这种说法不严谨)。 最后如果用并查集缩点的话一定要注意判断 i find(i) 因为缩完点之后这个点就是这个集合的代表。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N100010,MN*2,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int e[M],ne[M],h[N],idx;
int p[N],tot;
int d[N];
bool st[N];
struct Query
{int a,b;char op;
}q[N];void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}int find(int x)
{return xp[x]? x:p[x]find(p[x]);
}int topsort()
{int sum0,s0;int f1,f2; f1f20;queueintq;for(int i0;in;i) if(!d[i]ifind(i)) q.push(i),s; else if(ifind(i)) s;if(q.size()1) f11;while(q.size()){int cnt0; sum;int uq.front(); q.pop();for(int ih[u];~i;ine[i]){int je[i];if(--d[j]0) q.push(j),cnt;}if(cnt1) f11;}if(sum!s) f21;if(f1f2) return 2;else if(f2) return 2;else if(f1) return 1;else return 0;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);while(scanf(%d%d,n,m)!EOF){idx0; tot0;for(int i0;in;i) p[i]i,h[i]-1,d[i]0,st[i]0;for(int i1;im;i){int a,b; char op[2];scanf(%d%s%d,a,op,b);if(*op) p[find(a)]find(b);else q[tot]{a,b,op[0]};}for(int i1;itot;i){int aq[i].a,bq[i].b;st[a]1; st[b]1;char opq[i].op;afind(a); bfind(b);if(op) d[a],add(b,a);else d[b],add(a,b);}int ttopsort();if(t2) puts(CONFLICT);else if(t1) puts(UNCERTAIN);else puts(OK);}return 0;
}
/**/
