Pagini recente » Cod sursa (job #99773) | Cod sursa (job #768894) | Cod sursa (job #2044108) | Cod sursa (job #2972352) | Cod sursa (job #1167351)
#include <fstream>
#include <vector>
#include <stack>
#define NM 100010
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M, K;
vector<int> G[NM];
int Index[NM], LowLink[NM];
stack<int> Stack;
bool InStack[NM];
vector< vector<int> > Components;
void DF (int node)
{
Index[node]=LowLink[node]=++K;
InStack[node]=1;
Stack.push(node);
for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
if (Index[*it]==0)
{
DF(*it);
LowLink[node]=min(LowLink[node], LowLink[*it]);
}
else
if (InStack[*it])
LowLink[node]=min(LowLink[node], Index[*it]);
if (LowLink[node]>=Index[node])
{
vector<int> Aux;
for (; !Stack.empty() && Stack.top()!=node; InStack[Stack.top()]=0, Stack.pop())
Aux.push_back(Stack.top());
if (!Stack.empty() && Stack.top()==node)
{
Aux.push_back(Stack.top());
InStack[Stack.top()]=0;
Stack.pop();
}
Components.push_back(Aux);
}
}
int main ()
{
f >> N >> M;
for (int i=1; i<=M; i++)
{
int a, b;
f >> a >> b;
G[a].push_back(b);
}
for (int i=1; i<=N; i++)
if (Index[i]==0)
DF(i);
g << Components.size() << '\n';
for (size_t i=0; i<Components.size(); i++)
{
for (vector<int>::iterator it=Components[i].begin(); it!=Components[i].end(); ++it)
g << (*it) << ' ';
g << '\n';
}
f.close();
g.close();
return 0;
}