1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
|
#include<iostream> #include<cstring> #include<climits> #include<cstdio> #include<cctype> #include<vector> #include<cmath> #include<queue> #include<stack> #include<map> #define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c)) #define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c)) #define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c)) #define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c)) #define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c)) #define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c)) #define lowbit(x) x&(-x) #define LeftChild(x) x<<1 #define RightChild(x) (x<<1)+1 #define RevEdge(x) x^1 #define FILE_IN(x) freopen(x,"r",stdin); #define FILE_OUT(x) freopen(x,"w",stdout); #define CLOSE_IN() fclose(stdin); #define CLOSE_OUT() fclose(stdout); #define IOS(x) std::ios::sync_with_stdio(x) #define Dividing() printf("-----------------------------------n"); namespace FastIO{ const int BUFSIZE = 1 << 20; char ibuf[BUFSIZE],*is = ibuf,*its = ibuf; char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE; inline char (){ if(is == its) its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin); return (is == its)?EOF:*is++; } inline int getint(){ int res = 0,neg = 0,ch = getch(); while(!(isdigit(ch) || ch == '-') && ch != EOF) ch = getch(); if(ch == '-'){ neg = 1;ch = getch(); } while(isdigit(ch)){ res = (res << 3) + (res << 1)+ (ch - '0'); ch = getch(); } return neg?-res:res; } inline void flush(){ fwrite(obuf,1,os - obuf,stdout); os = obuf; } inline void putch(char ch){ *os++ = ch; if(os == ot) flush(); } inline void putint(int res){ static char q[10]; if(res == 0) putch('0'); else if(res < 0){putch('-');res = -res;} int top = 0; while(res){ q[top++] = res % 10 + '0'; res /= 10; } while(top--) putch(q[top]); } inline void space(bool x){ if(!x) putch('n'); else putch(' '); } } inline void read(int &x){ int rt = FastIO::getint(); x = rt; } inline void print(int x,bool enter){ FastIO::putint(x); FastIO::flush(); FastIO::space(enter); }
const int MAXN = 1e5 + 10; const int MAXM = 3e5 + 10; int n, m, EDGE[MAXM][2], head[MAXN], cnt, tot, deg[MAXN]; int low[MAXN], dfn[MAXN], sum[MAXN], indexs, Belong[MAXN]; std::stack<int> sta; struct Edge{int next, to;}Graph[MAXM << 1];
inline void clear() { cnt = 0; memset(head, 0, sizeof head); } inline void Add_Edge(int from, int to) { Graph[++cnt] = (Edge) {head[from], to}; head[from] = cnt; } inline void Tarjan(int u) { dfn[u] = low[u] = ++indexs; sta.push(u); for(int i = head[u]; i; i = Graph[i].next) { int v = Graph[i].to; if(!dfn[v]) { Tarjan(v); low[u] = std::min(low[u], low[v]); } else if(!Belong[v]) low[u] = std::min(low[u], dfn[v]); } if(low[u] == dfn[u]) { Belong[u] = ++tot; sum[tot]++; while(sta.top() != u) { Belong[sta.top()] = tot; sum[tot]++; sta.pop(); } sta.pop(); } } double ans; bool flag;
int main(int argc,char *argv[]){ scanf("%d %d", &n, &m); FOR(i, 1, m, 1) { scanf("%d %d", &EDGE[i][0], &EDGE[i][1]); Add_Edge(EDGE[i][0], EDGE[i][1]); } FOR(i, 1, n, 1) if(!dfn[i]) Tarjan(i); clear(); FOR(i, 1, m, 1) { if(Belong[EDGE[i][0]] == Belong[EDGE[i][1]]) continue; deg[Belong[EDGE[i][1]]]++; Add_Edge(Belong[EDGE[i][0]], Belong[EDGE[i][1]]); } FOR(u, 1, tot, 1) { if(!flag && !deg[u] && sum[u] == 1) { bool vis = false; for(int i = head[u]; i; i = Graph[i].next) { int v = Graph[i].to; if(deg[v] == 1) vis = true; } if(!vis) flag = true; } if(!deg[u]) ans++; } if(flag) ans--; ans = 1.0 - (double)ans / (double)n; printf("%.6lfn", ans); return 0; }
|
近期评论