Pagini recente » Cod sursa (job #2011772) | Cod sursa (job #1364) | Cod sursa (job #2189853) | Cod sursa (job #1004927) | Cod sursa (job #880868)
Cod sursa(job #880868)
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;
#define forEach(G) for(typeof (G).begin() it = (G).begin(); it != (G).end(); ++it)
#define pb push_back
#define maxn 100005
#define cout out
int n,m;
vector<int> graf[maxn];
vector< vector<int> > comp;
int index[maxn];
int lowest[maxn];
int cr;
bool good[maxn];
stack<int> S;
ifstream in("ctc.in");
ofstream out("ctc.out");
void read()
{
int a,b;
in >> n >> m;
while(m--)
{
in >> a >> b;
graf[a].push_back(b);
}
}
void dfs(int nod)
{
index[nod] = ++cr;
lowest[nod] = cr;
S.push(nod);
good[nod]=1;
forEach(graf[nod])
{
if(!lowest[*it])
dfs(*it);
if(good[*it])
lowest[nod] = min(lowest[nod],lowest[*it]);
}
if(index[nod] == lowest[nod])
{
vector<int> dat;
int x;
do
{
x = S.top();
S.pop();
dat.pb(x);
good[x]=0;
}
while(x != nod);
comp.pb(dat);
}
}
void print()
{
cout << comp.size() << "\n";
int i;
for(i=0;i<comp.size();++i)
{
forEach(comp[i])
cout << *it << " ";
cout << "\n";
}
}
int main()
{
read();
int i;
for(i=1;i<=n;++i)
if(!index[i])
dfs(i);
print();
return 0;
}