Pagini recente » Cod sursa (job #3122862) | Cod sursa (job #582132) | Cod sursa (job #60357) | Cod sursa (job #552770) | Cod sursa (job #2175581)
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
vector < int > v1[Nmax];
vector < int > v2[Nmax];
vector < int > v3[Nmax];
int x,y,n,m,i,j , viz[Nmax],nrcomp,l;
stack < int > st;
inline void read()
{
f >> n >> m;
for(i = 1;i <= m;i++)
{
f >> x >> y;
v1[x].push_back(y);
v2[y].push_back(x);
}
}
inline void dfs1(int nod)
{
viz[nod] = 1;
for(int i = 0,l = v1[nod].size(); i < l;i++)
if(viz[v1[nod][i]] == 0)
dfs1(v1[nod][i]);
st.push(nod);
}
inline void dfs2(int nod)
{
viz[nod] = -1;
for(int i = 0,l = v2[nod].size(); i < l;i++)
if(viz[v2[nod][i]] != -1)
dfs2(v2[nod][i]);
v3[nrcomp].push_back(nod);
}
void afisare()
{
g << nrcomp << '\n';
for(i = 1;i <= nrcomp;i++)
{
for(j = 0,l = v3[i].size();j < l;j++)
g << v3[i][j] << " ";
g << '\n';
}
}
int main()
{
read();
for(i = 1;i <= n;i++)
if(not viz[i])
dfs1(i);
while(not st.empty())
{
if(viz[st.top()] == -1)
{
st.pop();
continue;
}
nrcomp++;
dfs2(st.top());
st.pop();
}
afisare();
return 0;
}