Pagini recente » Cod sursa (job #442204) | Cod sursa (job #1818267) | Cod sursa (job #141103) | Cod sursa (job #3156429) | Cod sursa (job #2669741)
#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> muchii1[NMAX] , muchii2[NMAX] , H;
int n , m;
bool viz[NMAX];
vector <vector <int> > ans;
void DFS1(int nod)
{
viz[nod] = 1;
for(int i = 0 ; i < muchii1[nod].size() ; i ++)
if(!viz[muchii1[nod][i]])
DFS1(muchii1[nod][i]);
H.push_back(nod);
}
void DFS2(int nod)
{
viz[nod] = 1;
for(int i = 0 ; i < muchii2[nod].size() ; i ++)
if(!viz[muchii2[nod][i]])
DFS2(muchii2[nod][i]);
ans.back().push_back(nod);
}
int main()
{
fin >> n >> m;
for(int i = 1 ; i <= m ; i ++)
{
int x , y;
fin >> x >> y;
muchii1[x].push_back(y);
muchii2[y].push_back(x);
}
for(int i = 1 ; i <= n ; i ++)
if(!viz[i])
DFS1(i);
memset(viz , 0 , sizeof(viz));
for(int i = H.size() - 1 ; i >= 0 ; i --)
if(!viz[H[i]])
{
ans.push_back(vector <int> ());
DFS2(H[i]);
}
fout << ans.size() << '\n';
for(int i = 0 ; i < ans.size() ; i ++)
{
sort(ans[i].begin() , ans[i].end());
for(int j = 0 ; j < ans[i].size() ; j ++)
fout << ans[i][j] << ' ';
fout << endl;
}
return 0;
}