Pagini recente » Cod sursa (job #493230) | Cod sursa (job #936817) | Cod sursa (job #1593806) | Cod sursa (job #1918718) | Cod sursa (job #2335451)
#include<bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int>G[NMAX],GT[NMAX];
vector<int>Ras[NMAX];
bool used[NMAX];
int care[NMAX];
vector<int>Ordine;
int cate=1;
int n,m;
void DFS(int node)
{
used[node]=true;
for(auto i:G[node])
if(used[i]==false)
{
DFS(i);
}
Ordine.push_back(node);
}
void DFST(int node,int unde)
{
care[node]=unde;
for(auto i:GT[node])
{
if(care[i]==0)
DFST(i,unde);
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;++i)
{
int x,y;
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i=1;i<=n;++i)
{
if(used[i]==false)
{
DFS(i);
}
}
for(;Ordine.size();Ordine.pop_back())
{
if(care[Ordine.back()]==0)
{
DFST(Ordine.back(),cate);
cate++;
}
}
for(int i=1;i<=n;++i)
Ras[care[i]].push_back(i);
g<<cate-1<<'\n';
for(int i=1;i<cate;++i)
{
for(auto j:Ras[i])
g<<j<<' ';
g<<'\n';
}
}