Pagini recente » Cod sursa (job #405329) | Cod sursa (job #960300) | Cod sursa (job #3195437) | Cod sursa (job #1850667) | Cod sursa (job #2390514)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> v[200005];
vector<int> vt[200005];
stack<int> st;
vector<int> sol[200005];
int n,m,x,y;
int fr[200005];
int nrct;
void dfs1(int nod)
{
fr[nod] = 1;
for (vector<int> :: iterator it = v[nod].begin(); it != v[nod].end();++it)
if (fr[*it] == 0)
dfs1(*it);
st.push(nod);
}
void dfs2(int nod)
{
fr[nod] = nrct;
for (vector<int> :: iterator it = vt[nod].begin(); it != vt[nod].end();++it)
if (fr[*it] == 0)
dfs2(*it);
sol[nrct].push_back(nod);
}
int main()
{
in>>n>>m;
for (int i = 1;i <= m;++i)
{
in>>x>>y;
v[x].push_back(y);
vt[y].push_back(x);
}
for (int i = 1;i <= n;++i)
if (fr[i] == 0) dfs1(i);
for (int i = 1;i <= n;++i) fr[i] = 0;
while (!st.empty())
{
int x = st.top();
st.pop();
if (fr[x]) continue;
++nrct;
dfs2(x);
}
out<<nrct<<"\n";
for (int i = 1;i <= nrct;++i)
{
for (vector<int> :: iterator it = sol[i].begin(); it != sol[i].end();++it)
out<<*it<<" ";
out<<"\n";
}
return 0;
}