懂事时理解原神

懂事时理解原神 の 传送门

看到 概率，再看到 完全正确。

还有这样例，只有 1.000 和 0.000，然后画个图。

可以发现，从 \(1\) 开始遍历，则点 \(2\) 的距离既可能是 \(1\)，又可能是 \(2\)，就会出错，即只要这个图有环，则一定会出错。

#include <iostream>
#include <cstring>
const int N=5e4+5;
int T,n,m,f[N],vis[N];
namespace Fread {
const int SIZE = 16;
char buf[SIZE], *S, *T;
inline char getchar() {
    if (S == T) {
        T = (S = buf) + fread(buf, 1, SIZE, stdin);
        if (S == T) return '\n';
    }
    return *S++;
}
}
namespace Fwrite {
const int SIZE = 65536;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
    fwrite(buf, 1, S - buf, stdout);
    S = buf;
}
inline void putchar(char c) {
    *S++ = c;
    if (S == T) flush();
}
struct NTR {
    ~ NTR() { flush(); }
} ztr;
}
#ifdef ONLINE_JUDGE
    #define getchar Fread :: getchar
    #define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
    template<typename T>
    Reader& operator >> (T& x) {
        char c = getchar();
        T f = 1;
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = getchar();
        }
        x = 0;
        while (c >= '0' && c <= '9') {
            x = (x * 10 + (c - '0'));
            c = getchar();
        }
        x *= f;
        return *this;
    }
    Reader& operator >> (char& c) {
        c = getchar();
        while (c == '\n' || c == ' ') c = getchar();
        return *this;
    }
    Reader& operator >> (char* str) {
        int len = 0;
        char c = getchar();
        while (c == '\n' || c == ' ') c = getchar();
        while (c != '\n' && c != ' ') {
            str[len++] = c;
            c = getchar();
        }
        str[len] = '\0';
        return *this;
    }
    Reader(){}
} cin;
const char endl = '\n';
struct Writer {
    template<typename T>
    Writer& operator << (T x) {
        if (x == 0) { putchar('0'); return *this; }
        if (x < 0) { putchar('-'); x = -x; }
        static int sta[45];
        int top = 0;
        while (x) { sta[++top] = x % 10; x /= 10; }
        while (top) { putchar(sta[top] + '0'); --top; }
        return *this;
    }
    Writer& operator << (char c) {
        putchar(c);
        return *this;
    }
    Writer& operator << (char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer& operator << (const char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer(){}
} cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
int find(int v) {return (f[v]==v?v:f[v]=find(f[v]));}
signed main() {
	cin>>T;
	while(T--) {
		cin>>n>>m;
		for(int i=1;i<=n;++i)	f[i]=i;
		memset(vis,0,sizeof(vis));
		while(m--) {
			int u,v;cin>>u>>v;
			u=find(u),v=find(v);
			if(u==v)	vis[u]=1;
			f[v]=u;
		}
		for(int i=1;i<=n;++i)
			if(find(1)==find(i)&&vis[i]) {
				cout<<"0.000"<<endl;goto CONTINUE;
			}
		cout<<"1.000"<<endl;
		CONTINUE:;
	}
	return 0;
}