Pagini recente » Cod sursa (job #2130333) | Cod sursa (job #970703) | Cod sursa (job #2336152) | Cod sursa (job #1784667) | Cod sursa (job #2780093)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<int> v[100100];
vector<int> w[100100];
int vizitat[100100];
stack<int> stiva;
int ctc;
vector<int> ans[100100];
int nou[100100], cnt;
void dfs(int nod)
{
vizitat[nod] = true;
for(auto it : v[nod])
{
if(!vizitat[it])
{
dfs(it);
}
}
stiva.push(nod);
}
void postdfs(int nod)
{
vizitat[nod] = true;
ans[ctc].push_back(nod);
for(auto it : w[nod])
{
if(!vizitat[it])
{
postdfs(it);
}
}
}
int main()
{
fin >> n >> m;
while(m--)
{
int x, y;
fin >> x >> y;
v[x].push_back(y);
w[y].push_back(x);
}
for(int i = 1; i <= n; i ++)
{
if(!vizitat[i])
{
dfs(i);
}
}
while(!stiva.empty())
{
nou[++cnt] = stiva.top();
stiva.pop();
}
for(int i = 1; i <= n; i ++)
{
vizitat[i] = false;
}
for(int i = 1; i <= cnt; i ++)
{
if(!vizitat[i])
{
ctc++;
postdfs(i);
}
}
fout << ctc << '\n';
for(int i = 1; i <= ctc; i ++)
{
sort(ans[i].begin(), ans[i].end());
for(auto it : ans[i])
{
fout << it << ' ';
}
fout << '\n';
}
return 0;
}