Pagini recente » Cod sursa (job #2050915) | Cod sursa (job #2441488) | Cod sursa (job #2663063) | Cod sursa (job #2162954) | Cod sursa (job #1131395)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#define NM 100010
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M, K, NR;
vector<int> G[NM];
vector<int> Component[NM];
int Level[NM], LowLink[NM];
bool In[NM];
stack<int> S;
void DoTarjan (int node)
{
Level[node]=LowLink[node]=++K;
S.push(node);
In[node]=1;
for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
{
if (!Level[*it])
DoTarjan(*it);
if (In[*it])
LowLink[node]=min(LowLink[node], LowLink[*it]);
}
if (LowLink[node]==Level[node])
{
++NR;
for (; !S.empty() && S.top()!=node; S.pop())
{
Component[NR].push_back(S.top());
In[S.top()]=0;
}
if (!S.empty() && S.top()==node)
{
Component[NR].push_back(S.top());
In[S.top()]=0;
S.pop();
}
}
}
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 (!Level[i])
DoTarjan(i);
g << NR << '\n';
for (int i=1; i<=NR; i++)
{
for (vector<int>::iterator it=Component[i].begin(); it!=Component[i].end(); ++it)
g << (*it) << ' ';
g << '\n';
}
f.close();
g.close();
return 0;
}