Pagini recente » Cod sursa (job #1067660) | Cod sursa (job #2742727) | Cod sursa (job #1461979) | Cod sursa (job #102306) | Cod sursa (job #2928588)
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int NMAX = 1e5+1;
vector<int> v[NMAX], inv[NMAX], st, comp[NMAX];
int n, m;
bool marked[NMAX];
void dfs(int nod, vector<int>& st, vector<int>* graph)
{
marked[nod] = 1;
for(int vecin : graph[nod])
if(!marked[vecin])
dfs(vecin, st, graph);
st.push_back(nod);
}
int main()
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
int x, y;
cin>>x>>y;
v[x].push_back(y);
inv[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(!marked[i])
dfs(i, st, v);
memset(marked, false, sizeof(marked));
int nr = 0;
while(st.size())
{
int i = st.back();
st.pop_back();
if(!marked[i])
{
nr++;
dfs(i, comp[nr], inv);
}
}
cout<<nr<<"\n";
for(int i=1; i<=nr; i++)
{
for(int nod : comp[i])
cout<<nod<<" ";
cout<<'\n';
}
return 0;
}