1 条题解

  • 0
    @ 2025-5-25 18:32:50
    #include <iostream>
    #include <bitset>
    using namespace std;
    #define AUTHOR "HEX9CF"
    
    bitset<1005> bs[1005];
    
    int main()
    {
    	int n, m;
    	int cnt = 0;
    	cin >> n >> m;
    	int c = n * (n - 1) / 2;
    	for (int i = 0; i < m; i++)
    	{
    		int a, b;
    		cin >> a >> b;
    		bs[a][b] = 1;
    	}
    	
    	for (int j = 1; j <= n; j++)
    	{
    		for (int i = 1; i <= n; i++)
    		{
    			// a > b, b > c
    			if (bs[i][j])
    			{
    				// a > c
    				bs[i] |= bs[j];
    			}
    		}
    	}
    	for (int i = 1; i <= n; i++)
    	{
    		cnt += bs[i].count();
    		// cout << bs[i].count() << endl;
    	}
    	// cout << cnt << endl;
    	cout << c - cnt << endl;
    	return 0;
    }
    
    
    • 1

    信息

    ID
    2276
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者