Pagini recente » Cod sursa (job #772328) | Cod sursa (job #3262877) | Cod sursa (job #2036672) | Cod sursa (job #788734) | Cod sursa (job #3265126)
#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, x, y, ctc;
vector<vector<int>> graf, graft, ans;
vector<int> viz, componente, ord;
void dfs(int node)
{
viz[node] = 1;
for(auto next:graf[node])
if(!viz[node])
dfs(next);
ord.push_back(node);
}
void dfst(int node)
{
viz[node] = 1;
componente[node] = ctc;
for(auto next:graft[node])
if(!viz[next])
dfst(next);
}
int main()
{
cin >> n >> m;
graf.assign(n+1, vector<int>());
graft.assign(n+1, vector<int>());
viz.resize(n+1);
componente.resize(n+1);
for(int i=1; i<=m; i++)
{
cin >> x >> y;
graf[x].push_back(y);
graft[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(!viz[i])
dfs(i);
viz.assign(n+1, 0);
for(int i=1; i<=n; i++)
if(!viz[i])
{
ctc++;
dfst(i);
}
ans.assign(ctc+1, vector<int>());
for(int i=1; i<=n; i++)
ans[componente[i]].push_back(i);
cout << ctc << '\n';
for(int i=1; i<=ctc; i++, cout << '\n')
for(int j=0; j<ans[i].size(); j++)
cout << ans[i][j] << " ";
return 0;
}