fork download
copy 
  1. #include<stdio.h>
  2. #include<list>
  3. #include<vector>
  4. #define MOD 1000000007
  5. using namespace std;
  6. int main()
  7. {
  8. 	int test,n,m,a,b;
  9. 	scanf("%d",&test);
  10. 	while(test--)
  11. 	{
  12. 		scanf("%d%d",&n,&m);
  13. 		vector <list<int> > input(n);
  14. 		list <int> qq;
  15. 		list <int>::iterator it;
  16. 		while(m--)
  17. 		{
  18. 			scanf("%d%d",&a,&b);
  19. 			a--,b--;
  20. 			input[a].push_back(b);
  21. 		}
  22. 		int visit[n],done[n];
  23. 		for(int i=0;i<n;i++)
  24. 			visit[i]=1,done[i]=0;
  25. 		int count=0;
  26. 		long long ans=1;
  27. 		for(int i=0;i<n;i++)
  28. 		{
  29. 			if(visit[i])
  30. 			{
  31. 				count++;
  32. 				int k=0;
  33. 				qq.push_back(i);
  34. 				visit[i]=0;
  35. 				done[i]=1;
  36. 				while(!qq.empty())
  37. 				{
  38. 					//for(it=qq.begin();it!=qq.end();it++) printf("%d ",*it);puts("");
  39. 					k++;
  40. 					int ff=qq.front();
  41. 					qq.pop_front();
  42. 					visit[ff]=0;
  43. 					while(!input[ff].empty())
  44. 					{
  45. 						int temp=input[ff].front();
  46. 						input[ff].pop_front();
  47. 						if(done[temp]) continue;
  48. 						qq.push_back(temp);
  49. 						done[temp]=1;
  50. 					}
  51. 				}
  52. 				ans*=(k);
  53. 				ans%=MOD;
  54. 			}
  55. 		}
  56. 		input.clear();
  57. 		printf("%d %lld\n",count,ans);
  58. 	}
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
3
4 2
1 2
2 3
5 3
1 2
2 3
1 3
6 3
1 2
3 4
5 6
stdout
copy 
2 3
3 3
3 8
https://ideone.com/9Ayvf5
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!