Pagini recente » Cod sursa (job #2104521) | Cod sursa (job #2375530) | Cod sursa (job #1573656) | Cod sursa (job #1705761) | Cod sursa (job #3353862)
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool dfs(int a, int k, vector <vector <int>>& v1, vector <int>& f){
int i;
if (a==k)
return true;
f[a]=1;
for (i=0; i<v1[a].size(); i++)
if (f[v1[a][i]]==0 && dfs(v1[a][i], k, v1, f))
return true;
return false;
}
bool path(int a, int k, vector <vector <int>>& v1){
vector <int> f(v1.size()+1, 0);
return dfs(a, k, v1, f);
}
vector <vector <int>> fid(int n, vector <vector <int>>& a){
int i,j;
vector <vector <int>> r;
vector <int> f(n+1, 0);
vector <vector <int>> v1(n+1);
for (i=0; i<a.size(); i++)
v1[a[i][0]].push_back(a[i][1]);
for (i=1; i<=n; i++)
if (f[i]==0){
vector <int> rr;
rr.push_back(i);
for (j=i+1; j<=n; j++)
if (f[j]==0 && path(i, j, v1) && path(j, i, v1)){
f[j]=1;
rr.push_back(j);
}
r.push_back(rr);
}
return r;
}
signed main()
{
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
int n,m,i,a,b,j;
cin >> n >> m;
vector <vector <int>> v;
for (i=0; i<m; i++){
cin >> a >> b;
v.push_back({a, b});
}
vector <vector<int>> r=fid(n, v);
cout << r.size() << '\n';
for (i=0; i<r.size(); i++){
for (j=0; j<r[i].size(); j++)
cout << r[i][j] << ' ';
cout << '\n';
}
return 0;
}