Pagini recente » Cod sursa (job #965917) | Cod sursa (job #1321237) | Cod sursa (job #1550725) | Cod sursa (job #873854) | Cod sursa (job #848068)
Cod sursa(job #848068)
#include<fstream>
#include<bitset>
#include<vector>
#include<stack>
#define NMAX 100002
#define MMAX 200002
using namespace std;
int n,m,nr;
int nivel;
int lowl[NMAX],level[NMAX];
vector <int> v[NMAX],comp[NMAX];
stack <int> S;
bitset <NMAX> viz;
ifstream in("ctc.in");
ofstream out("ctc.out");
void scan() {
int a,b;
in>>n>>m;
for (int i=1;i<=m;i++)
{
in>>a>>b;
v[a].push_back(b);
}
}
inline int min(int a,int b)
{
if (a<=b)
return a;
return b;
}
void componenta(int nod)
{
int a;
nr++;
do
{
a=S.top();
comp[nr].push_back(a);
viz[a]=false;
S.pop();
}
while (a!=nod);
}
void dfs(int nod)
{
nivel++;
level[nod]=nivel;
lowl[nod]=nivel;
viz[nod]=true;
S.push(nod);
for (vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
{
if (!level[*it])
{
dfs(*it);
lowl[nod]=min(lowl[nod],lowl[*it]);
}
else if (viz[*it]==true)
lowl[nod]=min(lowl[nod],level[*it]);
}
if (lowl[nod]==level[nod])
componenta(nod);
}
void print()
{
out<<nr<<"\n";
for (int i=1;i<=nr;i++)
{
for (vector<int>::iterator it=comp[i].end()-1;it>=comp[i].begin();it--)
out<<*it<<" ";
out<<"\n";
}
}
int main() {
scan();
for (int i=1;i<=n;i++)
{
if (!level[i]) dfs(i);
}
print();
return 0;
}